给定一颗根结点为 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 和 8500 之间。
- 树中的每个结点都有一个介于 0 和 25 之间的值。
解答
/**
* 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 {
String minStr;
StringBuilder sb = new StringBuilder();
public String smallestFromLeaf(TreeNode root) {
// dfs节点，在找到叶子节点前，将节点入栈
dfsGetMinStr(root);
return minStr;
}
// 递归遍历树，当遍历到叶子节点时，将根节点到当前叶子节点形成的路径对应的字符串，
// 更新至最小字典序字符串变量中
private void dfsGetMinStr(TreeNode node) {
if (node == null) return;
sb.insert(0, (char) (node.val+'a'));
dfsGetMinStr(node.left);
dfsGetMinStr(node.right);
if (node.left == null && node.right == null) minStr = getMinStrInPairs(minStr, sb.toString());
// 路径已经构建完成，开始回退节点。从字符串中撤出当前节点对应的字符(即本轮递归中字符串首元素字符)
sb.deleteCharAt(0);
}
// 获取一对字符串中，字典序较小的字符串
private String getMinStrInPairs(String str1, String str2) {
if (str1 == null) return str2;
if (str2 == null) return str1;
int len = Math.min(str1.length(), str2.length());
for (int i = 0; i < len; i++) {
if (str1.charAt(i) < str2.charAt(i)) return str1;
if (str1.charAt(i) > str2.charAt(i)) return str2;
}
return str1.length() == len ? str1 : str2;
}
}
