Medium

题目描述

给定一个二叉树的根节点 root，树中每个节点都有一个范围在 [0, 25] 内的值，分别代表字母 'a' 到 'z'。

返回按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

提醒，任何较短的字符串前缀在字典序上都是较小的。

  • 例如，"ab" 在字典序上比 "aba" 小。

叶结点是指没有子节点的节点。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 树中节点数目在范围 [1, 8500] 内
  • 0 <= Node.val <= 25

解题思路

解题思路

这道题要求找到从叶节点到根节点路径组成的字典序最小字符串。关键观察是我们需要：

  1. 遍历所有叶节点到根节点的路径：使用深度优先搜索（DFS）遍历整棵树，当到达叶节点时记录路径。

  2. 构建字符串：由于题目要求是从叶节点开始到根节点结束，而我们在DFS过程中是从根到叶，所以需要反转路径来构建字符串。

  3. 字典序比较：在所有可能的路径字符串中找到字典序最小的那个。注意字典序比较的特性：较短的前缀总是更小。

实现方案：

  • 使用DFS递归遍历树
  • 维护当前路径的字符串
  • 当到达叶节点时，将当前路径翻转后与全局最小字符串比较更新
  • 由于我们在递归中是从根向叶构建路径，到叶节点时需要翻转字符串

优化点：可以在DFS过程中进行剪枝，如果当前路径已经比已知最小字符串大，可以提前返回。但由于字符串比较的复杂性，基础实现已经足够高效。

代码实现

class Solution {
public:
    string smallestFromLeaf(TreeNode* root) {
        string result = "";
        string path = "";
        dfs(root, path, result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, string& path, string& result) {
        if (!node) return;
        
        path += char('a' + node->val);
        
        if (!node->left && !node->right) {
            string candidate = path;
            reverse(candidate.begin(), candidate.end());
            if (result.empty() || candidate < result) {
                result = candidate;
            }
        }
        
        dfs(node->left, path, result);
        dfs(node->right, path, result);
        
        path.pop_back();
    }
};

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        self.result = ""
        
        def dfs(node, path):
            if not node:
                return
            
            path.append(chr(ord('a') + node.val))
            
            if not node.left and not node.right:
                candidate = ''.join(reversed(path))
                if not self.result or candidate < self.result:
                    self.result = candidate
            
            dfs(node.left, path)
            dfs(node.right, path)
            
            path.pop()
        
        dfs(root, [])
        return self.result

public class Solution {
    private string result = "";
    
    public string SmallestFromLeaf(TreeNode root) {
        List<char> path = new List<char>();
        DFS(root, path);
        return result;
    }
    
    private void DFS(TreeNode node, List<char> path) {
        if (node == null) return;
        
        path.Add((char)('a' + node.val));
        
        if (node.left == null && node.right == null) {
            var candidate = new string(path.ToArray());
            var reversed = new string(candidate.Reverse().ToArray());
            if (string.IsNullOrEmpty(result) || string.Compare(reversed, result) < 0) {
                result = reversed;
            }
        }
        
        DFS(node.left, path);
        DFS(node.right, path);
        
        path.RemoveAt(path.Count - 1);
    }
}

var smallestFromLeaf = function(root) {
    let result = "";
    
    function dfs(node, path) {
        if (!node) return;
        
        path.push(String.fromCharCode(97 + node.val));
        
        if (!node.left && !node.right) {
            const candidate = path.slice().reverse().join('');
            if (!result || candidate < result) {
                result = candidate;
            }
        }
        
        dfs(node.left, path);
        dfs(node.right, path);
        
        path.pop();
    }
    
    dfs(root, []);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × h)n是节点数，h是树的高度。需要遍历所有节点，每个叶节点处需要构造和比较长度为h的字符串
空间复杂度O(h)递归调用栈和路径存储的空间，h是树的高度

相关题目