前言
Weekly Contest 122 的 从叶结点开始的最小字符串：
给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 ‘a’ 到 ‘z’：值 0 代表 ‘a’，值 1 代表 ‘b’，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 “ab” 比 “aba” 要小。叶结点是指没有子结点的结点。）
示例 1：
输入：[0,1,2,3,4,3,4]
输出：”dba”
示例 2：
输入：[25,1,3,1,3,0,2]
输出：”adz”
示例 3：
输入：[2,2,1,null,1,0,null,0]
输出：”abc”
提示：
给定树的结点数介于 1 和 1000 之间。
树中的每个结点都有一个介于 0 和 25 之间的值。
解题思路
此题可以看做是一种特殊的中序遍历，只是递归的过程中需要比较左右子树值。
实现代码
/**
* 988. 从叶结点开始的最小字符串
* 中序遍历的基础上改造
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
* @param root
* @return
*/
public String smallestFromLeaf(TreeNode root) {
// 节点值为 [0,25]，所以需要加上 ’a’ 来获得对应的 char
char c = (char)(‘a’ + root.val);
if (root.left == null && root.right == null) {// 无左右子树
return “” + c;
} else if (root.left == null) {// 左子树为空，遍历右子树
String str = smallestFromLeaf(root.right);
return str + c;//
} else if (root.right == null) {// 右子树为空，遍历左子树
return smallestFromLeaf(root.left) + c;
} else {// 左右子树都不为空
String s1 = smallestFromLeaf(root.left);
String s2 = smallestFromLeaf(root.right);
if (s1.compareTo(s2) < 0) {// 比较左右子树的最小字符串
return s1 + c;
} else {
return s2 + c;
}
}
}