988-从叶结点开始的最小字符串

r囧r小猫 2022-03-07 12:44 137阅读 0赞

## 前言 ##

[Weekly Contest 122][]的 [从叶结点开始的最小字符串][Link 1]：

> 给定一颗根结点为 `root` 的二叉树，书中的每个结点都有一个从 `0` 到 `25` 的值，分别代表字母 `'a'` 到 `'z'`：值 `0` 代表 `'a'`，值 `1` 代表 `'b'`，依此类推。
> 
> 找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
> 
> *（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 `"ab"` 比 `"aba"` 要小。叶结点是指没有子结点的结点。）*
> 
> **示例1：**  
> ![tree1.png][]
> 
>     输入：[0,1,2,3,4,3,4]
>     输出："dba"
> 
> **示例2：**  
> ![tree2.png][]
> 
>     输入：[25,1,3,1,3,0,2]
>     输出："adz"
> 
> **示例3：**  
> ![tree3.png][]
> 
>     输入：[2,2,1,null,1,0,null,0]
>     输出："abc"
> 
> **提示：**
> 
> 1.  给定树的结点数介于 `1` 和 `1000` 之间。
> 2.  树中的每个结点都有一个介于 `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;
                }
            }
        }

[Weekly Contest 122]: https://leetcode-cn.com/contest/weekly-contest-122
[Link 1]: https://leetcode-cn.com/contest/weekly-contest-122/problems/smallest-string-starting-from-leaf/
[tree1.png]: /images/20220307/039a600338fd408f92b74e1a5fce2fad.png
[tree2.png]: /images/20220307/dfd021eec1f14f809e3c1760ae64d993.png
[tree3.png]: /images/20220307/9fcbf3c7427546bbb6b84d0badb3980a.png