从叶结点开始的最小字符串 图解题解

这道题到底在问什么

输入

root=[0,1,2,3,4,3,4]

输出

"dba"

最优解：一步一步想明白

1. 3记住「下行追加、到叶成串比最小、回溯弹出」，下面每帧都在套它。
2. 4从根开始 DFS开局路径为空、最小串还没有。DFS 从根出发，沿左右孩子一路下探到每个叶子。
3. 5path = a走到节点 a（紫色），把它追加进当前路径，现在根到这里是 a。它还有孩子，继续往下走。
4. 6path = ab走到节点 b（紫色），把它追加进当前路径，现在根到这里是 ab。它还有孩子，继续往下走。
5. 7path = abd走到节点 d（紫色），把它追加进当前路径，现在根到这里是 abd。它没有孩子，是个叶子。
6. 8候选 dba ← 更小到达叶子 d。把路径反过来（叶→根）拼成候选串 “dba”。它比之前的最小串更小，刷新最小为 “dba”。
7. 9弹出 d节点 d 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
8. 10path = abe走到节点 e（紫色），把它追加进当前路径，现在根到这里是 abe。它没有孩子，是个叶子。
9. 11候选 eba到达叶子 e。把路径反过来（叶→根）拼成候选串 “eba”。它不比当前最小 “dba” 小，保持不变。
10. 12弹出 e节点 e 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
11. 13弹出 b节点 b 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
12. 14path = ac走到节点 c（紫色），把它追加进当前路径，现在根到这里是 ac。它还有孩子，继续往下走。
13. 15path = acd走到节点 d（紫色），把它追加进当前路径，现在根到这里是 acd。它没有孩子，是个叶子。
14. 16候选 dca到达叶子 d。把路径反过来（叶→根）拼成候选串 “dca”。它不比当前最小 “dba” 小，保持不变。
15. 17弹出 d节点 d 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
16. 18path = ace走到节点 e（紫色），把它追加进当前路径，现在根到这里是 ace。它没有孩子，是个叶子。
17. 19候选 eca到达叶子 e。把路径反过来（叶→根）拼成候选串 “eca”。它不比当前最小 “dba” 小，保持不变。
18. 20弹出 e节点 e 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
19. 21弹出 c节点 c 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
20. 22弹出 a，结束根节点 a 的左右子树都试完了，把它从路径弹出，DFS 到此全部结束——所有根到叶的路径都比过了。
21. 23答案 = dba四个叶子分别给出 dba、eba、dca、eca，字典序最小的是 “dba”，就是答案。整个过程一次 DFS、回溯时弹出，路径始终保持「根到当前」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

#include <string>
#include <algorithm>
using namespace std;

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {} };

class Solution {
public:
    string smallestFromLeaf(TreeNode* root) {
        string path, best;
        dfs(root, path, best);
        return best;
    }
private:
    void dfs(TreeNode* node, string& path, string& best) {
        if (!node) return;
        path.push_back(char('a' + node->val));
        if (!node->left && !node->right) {
            string cand(path.rbegin(), path.rend());
            if (best.empty() || cand < best) best = cand;
        } else {
            dfs(node->left, path, best);
            dfs(node->right, path, best);
        }
        path.pop_back();
    }
};

import java.util.*;

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }

class Solution {
    private String best = null;
    public String smallestFromLeaf(TreeNode root) {
        best = null;
        dfs(root, new StringBuilder());
        return best == null ? "" : best;
    }
    private void dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.append((char)('a' + node.val));
        if (node.left == null && node.right == null) {
            String cand = path.reverse().toString();
            path.reverse();
            if (best == null || cand.compareTo(best) < 0) best = cand;
        } else {
            dfs(node.left, path);
            dfs(node.right, path);
        }
        path.deleteCharAt(path.length() - 1);
    }
}

复杂度

面试官可能追问