二叉树的所有路径 图解题解

这道题到底在问什么

树

[1,2,3,4,5,null,6]

输出

["1->2->4", "1->2->5", "1->3->6"]

说明

每条路径都从根 1 开始,到一个叶子结束

先想最直接的笨办法

笨办法也是好办法:顺着树一杆子捅到底(深度优先)。每进一个节点,路径末尾就多一个它;一旦发现是叶子,这条路就完整了,存下来;然后退回岔路口换条路再扎。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法也是好办法:顺着树一杆子捅到底(深度优先)。每进一个节点,路径末尾就多一个它;一旦发现是叶子,这条路就完整了,存下来;然后退回岔路口换条路再扎。
2. 4根=1, 叶子=4 / 5 / 6绿色的 4、5、6 是叶子(下面再没有孩子)。我们的目标:找出根 1 到每个叶子的完整走法,一共会有三条路。
3. 5只有叶子才是路径终点蓝色的 1、2、3 是中间节点(还有孩子),路过但不收;绿色的 4、5、6 才是叶子,是路径的终点。心里先有这张图,走起来就清楚了。
4. 6所以输出顺序是先把 2 这边两条走完("1->2->4"、"1->2->5"),再走 3 这边("1->3->6")。理解这个「一头扎到底、再回头」的顺序,后面看每一帧就不会乱。
5. 7path = "1"从根 1 出发,当前路径就是 "1"。1 有孩子,不是叶子,继续往下探它的左孩子。
6. 8path = "1->2"进入 2,把它接到路径后面 → "1->2"。1 已经在路径里(变成路径节点)。2 还有孩子,继续往下探它的左孩子。
7. 9path = "1->2->4"进入 4,路径变成 "1->2->4"。先别急着收——得问一句:4 是叶子吗?
8. 104 左右都空 → 是叶子!4 左右都没孩子 → 是叶子,这条 "1->2->4" 走到头了,可以收。
9. 11结果 += "1->2->4"把 "1->2->4" 存进结果列表。这条分支探完了,接下来要往回退到 2,去看它还没走过的另一个孩子。
10. 12撤销 4, 回到 path = "1->2"从 4 退回 2:路径里的 4 被撤销,回到 "1->2"。4 这格标记成已探完(变灰)。2 还有个右孩子 5 没走,去探它。
11. 13path = "1->2->5"进入 5,路径变成 "1->2->5"。同样先判一句:5 是叶子吗?
12. 145 左右都空 → 是叶子!5 左右都没孩子 → 是叶子,"1->2->5" 走到头,收下第二条。
13. 15结果 += "1->2->5"把 "1->2->5" 也存进结果。5 探完,2 的左右孩子都走过了——该退回 2,再退回根 1 了。
14. 16撤销 5, 回到 path = "1->2"从 5 退回 2:5 被撤销并标记已探完,回到 "1->2"。2 的两个孩子(4、5)现在全是灰的——2 这棵子树彻底探完。
15. 17撤销 2, 回到 path = "1"继续退,从 2 退回 1,路径里的 2 也撤销,回到 "1"。整棵左子树(2 那一片)已探完(全灰)。
16. 181 左边走完,轮到右孩子 31 的左孩子 2 整片探完了。DFS 的规矩:左边走干净了才回头走右边。现在轮到 1 的右孩子 3。
17. 19path = "1->3"进入 1 的右孩子 3,路径变成 "1->3"。3 还有个右孩子 6,不是叶子,继续往下探。
18. 20path = "1->3->6"进入 6,路径变成 "1->3->6"。3 的左孩子是空,只有右孩子 6 这条路。
19. 216 左右都空 → 是叶子!6 左右都没孩子 → 是叶子,"1->3->6" 也走到头了,第三条路收下。
20. 22结果 += "1->3->6"把 "1->3->6" 存进结果。6 探完,退回 3、再退回 1——此时 1 的左右孩子都走过了,整棵树遍历结束。
21. 23结果 = ["1->2->4", "1->2->5", "1->3->6"]三条路径全找到:"1->2->4"、"1->2->5"、"1->3->6"。DFS + 回溯就是这样:深入到叶子收一条,退回换条路再深入,直到走遍所有分支。
22. 24为什么走 3 的时候路径不是 "1->2->5->3"?因为退回 1 时,2、4、5 已经被撤销了。「进来加、出去撤」让每条分支看到的都是干净的前缀。
23. 27本题用「按值传参」让撤销自动发生;若改成共享一个 list,就得手动 path.pop() 来撤销。两种写法本质都是这三步。认准它,全排列/子集/组合一类题全打通。
24. 29错误: 中间节点 1 / 2 也被收集如果忘了判叶子,走到 1 收一条 "1"、走到 2 又收一条 "1->2"……半截路径全冒出来了。必须确认「左右孩子都为空」才是真正的路径终点。

⚠️ 容易写错的地方

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

class Solution:
    def binaryTreePaths(self, root):
        res = []
        def dfs(node, path):
            if not node:
                return
            path = path + str(node.val)   # 把当前节点接上
            if not node.left and not node.right:  # 叶子
                res.append(path)          # 收一条完整路径
                return
            dfs(node.left,  path + '->')  # 探左
            dfs(node.right, path + '->') # 探右
        dfs(root, '')
        return res

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (root) dfs(root, "", res);
        return res;
    }
    void dfs(TreeNode* node, string path, vector<string>& res) {
        path += to_string(node->val);          // 接上当前节点
        if (!node->left && !node->right) {     // 叶子
            res.push_back(path);               // 收一条
            return;
        }
        if (node->left)  dfs(node->left,  path + "->", res);
        if (node->right) dfs(node->right, path + "->", res);
    }
};

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root != null) dfs(root, "", res);
        return res;
    }
    private void dfs(TreeNode node, String path, List<String> res) {
        path += node.val;                       // 接上当前节点
        if (node.left == null && node.right == null) {  // 叶子
            res.add(path);                      // 收一条
            return;
        }
        if (node.left != null)  dfs(node.left,  path + "->", res);
        if (node.right != null) dfs(node.right, path + "->", res);
    }
}

复杂度

面试官可能追问