LeetCode 988. Smallest String Starting From Leaf

Smallest String Starting From Leaf"/>

LeetCode 988. Smallest String Starting From Leaf

原题链接在这里：/

题目：

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find 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: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

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

Example 3:

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

Note:

1. The number of nodes in the given tree will be between 1 and 8500.
2. Each node in the tree will have a value between 0 and 25.

题解：

Do dfs and get all possible results. Maintain the smallest one.

Update the res only at leaf node, but not when node is null. Otherwise, it would get wrong result. 

e.g. [1,2], if update res at null, when iterating right child, since it is null, current string is "a", smaller than existing "ba", it would update res. But actually it is not string starting from leaf.

For questions specifically mentioned leaf, should update node only at leaf node.

Time Complexity: O(n).

Space: O(h).

AC Java: 

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     String res = "~";
12     
13     public String smallestFromLeaf(TreeNode root) {
14         if(root == null){
15             return res;
16         }
17         
18         dfs(root, new StringBuilder());
19         return res;
20     }
21     
22     private void dfs(TreeNode root, StringBuilder sb){
23         if(root == null){
24             return;
25         }
26         
27         sb.insert(0, (char)('a'+root.val));
28         
29         // Update res only at leaf node 
30         if(root.left == null && root.right == null){
31             if(sb.toString()pareTo(res) < 0){
32                 res = sb.toString();
33             }
34         }
35 
36         dfs(root.left, sb);
37         dfs(root.right, sb);
38 
39         sb.deleteCharAt(0);
40     }
41 }

类似Sum Root to Leaf Numbers, Binary Tree Paths.

转载于:.html