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

前言

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

输入：[0,1,2,3,4,3,4]
输出："dba"

输入：[25,1,3,1,3,0,2]
输出："adz"

输入：[2,2,1,null,1,0,null,0]
输出："abc"

解题思路

此题可以看做是一种特殊的中序遍历，只是递归的过程中需要比较左右子树值。

实现代码

/**
     * 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;
            }
        }
    }