988. Smallest String Starting From Leaf

Medium

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.

• For example, "ab" is lexicographically smaller than "aba".

A leaf of a node is a node that has no children.

Example 1:

• Input: root = [0,1,2,3,4,3,4]
• Output: "dba"

Example 2:

• Input: root = [25,1,3,1,3,0,2]
• Output: "adz"

Example 3:

• Input: root = [2,2,1,null,1,0,null,0]
• Output: "abc"

Constraints:

• The number of nodes in the tree is in the range [1, 8500].
• 0 <= Node.val <= 25

    /**
    * Definition for a binary tree node.
    * class TreeNode {
    *     public $val = null;
    *     public $left = null;
    *     public $right = null;
    *     function __construct($val = 0, $left = null, $right = null) {
    *         $this->val = $val;
    *         $this->left = $left;
    *         $this->right = $right;
    *     }
    * }
    */
    class Solution {

        /**
        * @param TreeNode $root
        * @return String
        */
        function smallestFromLeaf($root) {
            $ans = "";
            $this->dfs($root, "", $ans);
            return $ans;
        }

        private function dfs($root, $path, &$ans) {
            if ($root == null)
            return;

            $path .= chr($root->val + ord('a'));

            if ($root->left == null && $root->right == null) {
                $path = strrev($path);
                if ($ans == "" || $ans > $path)
                    $ans = $path;
                    $path = strrev($path);  // Roll back.
            }

            $this->dfs($root->left, $path, $ans);
            $this->dfs($root->right, $path, $ans);
            $path = substr($path, 0, -1);
        }
    }