前言
的 ：
给定一颗根结点为
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; } } }