Smallest String Starting From Leaf

Given therootof a binary tree, each node has a value from0to25representing the letters'a'to'z': a value of0represents'a', a value of1represents'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

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

前序遍历，注意一下退出的条件

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String smallestFromLeaf(TreeNode root) {
        if (root == null) {
            return null;
        }
        char ch = (char)('a' + root.val);
        String left  = smallestFromLeaf(root.left);
        String right = smallestFromLeaf(root.right);
        if (left == null && right == null) { // leaf
            return "" + ch;
        }
        if (left == null) {
            return right + ch;
        }
        if (right == null) {
            return left + ch;
        }
        if (left.compareTo(right) < 0) {
            return left + ch;
        } else {
            return right + ch;
        }
    }


}