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);
        }
    }

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

LinkedIn
GitHub

Blog

988. Smallest String Starting From Leaf

MD ARIFUL HAQUE

Join Our Newsletter. No Spam, Only the good stuff.

Related