题目链接：988. Smallest String Starting From Leaf

概述

题目给定一棵二叉树，每个节点值为0到25的值，分别对应a到z，求树中字典序最小的字符串。

思路

一开始想到的方法，就是去深度遍历，每个节点对应的字符串为min(左子树的字符串 + 当前节点值, 右子树的字符串 + 当前节点值)，

实现代码大致如下：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var smallestFromLeaf = function(root) {
    var res = "";
    
    let dfs = (node) => {
        if(node === null){
            return '';
        }
        
        let leftStr = dfs(node.left);
        let rightStr = dfs(node.right);
        let ch = String.fromCharCode(97 + node.val);
        var ret = "";
        if(leftStr == '' && rightStr == ''){
            ret = ch;
        }
        else if(leftStr == '' || rightStr == ''){
            ret = (leftStr != '' ? leftStr : rightStr) + ch;
        }
        else{
            ret = leftStr + ch < rightStr + ch ? leftStr + ch : rightStr + ch;
        }
        return ret;
    };
    return dfs(root);
};

但是！这段代码只能通过66/67的测试样例，

1	[25,1,null,0,0,1,null,null,null,0]

这个无法通过。

在看了评论区大神的说明后，明白了。

考虑 ab 和 abab以及节点值z，显然，ab < abab，abz > ababz。
本测试样例的树如下：

上述代码执行过程如下：

错误发生在第二层的节点b处。

如果只以子树的字符串为依据，由于不知道加上父亲节点之后，构成的字典序是否仍是较小的那个，所以在这边发生了错误。

想到这，也好修正了，只需要传入父亲节点的值，即可。

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var smallestFromLeaf = function(root) {
    var res = "";
    
    let dfs = (node, s) => {
        if(node === null){
            return '{';  // { 的 ascii 码大于 z
        }
        
        s = String.fromCharCode(97 + node.val) + s;
        let leftStr = dfs(node.left, s);
        let rightStr = dfs(node.right, s);
        var ret = "";
        if(leftStr == '{' && rightStr == '{'){
            ret = s;
        }
        else {
            ret = leftStr < rightStr ? leftStr : rightStr;
        }
        return ret;
    };
    return dfs(root, '');
};

题解合集

种星星

LeetCode题解|988. Smallest String Starting From Leaf

概述

思路

实现