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