Skip to content

Latest commit

 

History

History
155 lines (119 loc) · 3.88 KB

ext-binary-tree-paths.md

File metadata and controls

155 lines (119 loc) · 3.88 KB

257.二叉树的所有路径

https://leetcode-cn.com/problems/binary-tree-paths/

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：DFS

思路

DFS

以这个输入为例：

   1
 /   \
2     3
 \
  5
  • 想象一下，有一个小精灵拿着篮子站在了根节点 1，它把 1 放进了篮子里，接着，它的面前出现了两条路 2 和 3。
  • 小精灵使用影分身复制了一个自己和一个篮子，一个分身往左走，一个分身往右走。
  • 往左走的小精灵继续把 2 放进篮子，然后再往右下走把 5 放进篮子，这时候篮子是 [1,2,5]，由于在 5 没法继续前进了，这个篮子就被保存起来了。
  • 再回来看一开始往右走的小精灵，它往右下走到 3，把 3 装进篮子，这时候篮子是 [1,3]，由于没有路了，这个篮子也被保存了起来。
  • 小精灵最终得到了两个篮子 [1,2,5] 和 [1,3]。

回溯

如果用上回溯的话，我们可以想象成从始至终只有一个篮子。

  • 小精灵拿着篮子从 1 开始，此时篮子是 [1]，
  • 接着它先往左走，走到 2，篮子是 [1,2]，
  • 从 2 再往右走，走到 5，篮子是 [1,2,5]，到这里已经不能继续前进了，小精灵就把篮子里的东西复制一份保存起来，然后转身往回走，
  • 一边走一边把篮子里的东西往外扔，从 5 走回 2，此时篮子是 [1,2]，把 5 扔掉了，
  • 从 2 开始也没有其他还没走过的路了，所以回退到 1，此时篮子只剩 [1]。
  • 到了 1 这个位置，小精灵发现右边的路还没走，于是就往右边去捡东西了，这个过程跟之前往左走是一样的。

复杂度

  • 时间复杂度：$O(n)$，n 为二叉树的节点数。
  • 空间复杂度：$O(h)$，h 为二叉树的高度。

代码

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
    if (!root) return [];

    const ans = [];
    dfs(root, []);
    return ans;

    // *******************************
    function dfs(node, path) {
        if (!node) return;

        if (!node.left && !node.right) {
            ans.push([...path, node.val].join('->'));
            return;
        }

        dfs(node.left, [...path, node.val]);
        dfs(node.right, [...path, node.val]);
    }
};

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
    if (!root) return [];

    const ans = [];
    const path = [];
    dfs(root);
    return ans;

    // ******************************
    function dfs(node) {
        if (!node) return;

        path.push(node.val);

        if (!node.left && !node.right) {
            ans.push(path.join('->'));
            // 回溯
            path.pop();
            return;
        }

        dfs(node.left);
        dfs(node.right);
        // 回溯
        path.pop();
    }
};