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

本题来自 LeetCode：988. 从叶结点开始的最小字符串^[1]

题目描述

给定一颗根结点为  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(int x) { val = x; }
 * }
 */
class Solution {
    public String smallestFromLeaf(TreeNode root) {
        if(root == null) {
            return null;
        }
        return dfs(root, "");
    }

    public String dfs(TreeNode root, String path) {
        path = getLowAlphabet(root.val) + path;

        //  该节点为叶子节点
        if(root.left == null && root.right == null) {
            return path;
        }

        // 左子二叉树的最小字符串
        String leftPath = null;
        if(root.left != null) {
            leftPath = dfs(root.left, path);
        }
        // 右子二叉树的最小字符串
        String rightPath = null;
        if(root.right != null) {
            rightPath = dfs(root.right, path);
        }
        // 左子二叉树为空
        if(leftPath == null) {
            return rightPath;
        }
        // 右子二叉树为努力了
        if(rightPath == null) {
            return leftPath;
        }
        // 比较左、右二叉树的最小字符串
        return leftPath.compareTo(rightPath)  0 ? leftPath : rightPath;
    }

    public String getLowAlphabet(int val) {
        return String.valueOf(((char)(val + 'a')));
    }
}

复杂度分析：
时间复杂度： O(n)，遍历每个节点
空间复杂度： O(n)，每个节点会创建一个字符串

参考资料

988. 从叶结点开始的最小字符串: https://leetcode-cn.com/problems/smallest-string-starting-from-leaf

原文始发于微信公众号（xiaogan的技术博客）：