面试题 04.12. 求和路径

发表于 | 分类于
描述示例

用时：20min

因为是求 “ 每个节点出发的为sum的路径”

很明显就想到了回溯，因为是二叉树，所以就双递归。

外层递归用来找到所有的节点，内层用来算节点的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var pathSum = function(root, sum) {
    var res = 0
    var dfs = function (root,total,visited) {
        if (!root) return 
        if (total + root.val == sum) {
            res++
        } else if (total + root.val > sum) {
            return 
        } 
        dfs(root.left,total + root.val,[...visited,root.val])
        dfs(root.right,total + root.val,[...visited,root.val])
    }
    var dfs_outer = function (root) {
        if (!root )return 
        root.left && dfs_outer(root.left)
        dfs(root,0,[])
        root.right && dfs_outer(root.right)
    }
    dfs_outer(root)
    return res
};