988-從葉結點開始的最小字串
摘要：
前言
Weekly Contest 122 的 從葉結點開始的最小字串 ：
給定一顆根結點為 root 的二叉樹，書中的每個結點都有一個從 0 到 25 的值，分別代表字母 'a' 到 'z' ：值 0 代表 'a' ，值 ...
前言
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;
}
}
}