Tree
Depth-First Search
String
Backtracking
Binary Tree
Description
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
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def smallestFromLeaf ( self , root : TreeNode ) -> str :
ans = chr ( ord ( 'z' ) + 1 )
def dfs ( root , path ):
nonlocal ans
if root :
path . append ( chr ( ord ( 'a' ) + root . val ))
if root . left is None and root . right is None :
ans = min ( ans , '' . join ( reversed ( path )))
dfs ( root . left , path )
dfs ( root . right , path )
path . pop ()
dfs ( root , [])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private StringBuilder path ;
private String ans ;
public String smallestFromLeaf ( TreeNode root ) {
path = new StringBuilder ();
ans = String . valueOf (( char ) ( 'z' + 1 ));
dfs ( root , path );
return ans ;
}
private void dfs ( TreeNode root , StringBuilder path ) {
if ( root != null ) {
path . append (( char ) ( 'a' + root . val ));
if ( root . left == null && root . right == null ) {
String t = path . reverse (). toString ();
if ( t . compareTo ( ans ) < 0 ) {
ans = t ;
}
path . reverse ();
}
dfs ( root . left , path );
dfs ( root . right , path );
path . deleteCharAt ( path . length () - 1 );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
string ans = "" ;
string smallestFromLeaf ( TreeNode * root ) {
string path = "" ;
dfs ( root , path );
return ans ;
}
void dfs ( TreeNode * root , string & path ) {
if ( ! root ) return ;
path += 'a' + root -> val ;
if ( ! root -> left && ! root -> right ) {
string t = path ;
reverse ( t . begin (), t . end ());
if ( ans == "" || t < ans ) ans = t ;
}
dfs ( root -> left , path );
dfs ( root -> right , path );
path . pop_back ();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf ( root * TreeNode ) string {
ans := ""
var dfs func ( root * TreeNode , path string )
dfs = func ( root * TreeNode , path string ) {
if root == nil {
return
}
path = string ( 'a' + root . Val ) + path
if root . Left == nil && root . Right == nil {
if ans == "" || path < ans {
ans = path
}
return
}
dfs ( root . Left , path )
dfs ( root . Right , path )
}
dfs ( root , "" )
return ans
}
GitHub