🥈34. 二叉树中和为某一值的路径（LeetCode 113）@

🥈Medium

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

节点总数 <= 10000

题解

今天字节面试原题，写的有问题，面试遇到了三个月前的面试官和原题，还是一团糟！今晚上得要好好复习，不能偷懒，明天面试一定要顺利！

谁能想到2021.1.11再一次面字节，又遇到这道题了呢！o(╥﹏╥)o。当时看明白之后也没有好好总结和复习。树方面还是很薄弱的

深度优先搜索

枚举每一条从根节点到叶节点的路径。当遍历到叶节点，且此时路径和恰好为目标和时，就是一条满足条件的路径。

Python

def pathSum(root, total):
    res=[]
    path=[]
    def dfs(node,total):
        if not root:
            return
        path.append(root.val)
        total -= root.val
        if not root.left and not root.right and total == 0:
            # 这里要注意添加的是深拷贝，不是原数组
            res.append(path[:])
        dfs(root.left,total)
        dfs(root.right,total)
        path.pop()
    dfs(root,total)
    return res

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    let res=[]
    let path=[]
    let dfs=function (node,sum){
        if (!node){
            return
        }
        path.push(node.val)
        sum-=node.val
        if (!node.left && !node.right && sum===0){
            let temp=path
            res.push(JSON.parse(JSON.stringify(path)))
        }
        dfs(node.left,sum)
        dfs(node.right,sum)
        path.pop()
    }
    dfs(root,sum)
    return res
};

复杂度分析

• 时间复杂度：。其中 是树的节点数。在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为，并且每一条路径的节点个数也为，因此要将这些路径全部添加进答案中，时间复杂度为
• 空间复杂度：，其中 N 是树的节点数。空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。

  广度优先搜索