113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
- Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
- 解法一，不用回溯
function hasPathsum(root,sum){
let res = []
const findPath = (root,sum,path) => {
if(!root) return
let newSum = sum - root.val;
path.push(root.val)
if(!root.left && !root.right && newSum === 0){
res.push(path)
}
findPath(root.left,newSum,path.slice())
findPath(root.right,newSum,path.slice())
}
findPath(root,sum,[])
return res;
}
- 解法二，DFS加回溯哦
function hasPathsum(root,sum){
let res = []
const findPath = (root,sum,path) => {
if(!root) return
let newSum = sum - root.val;
path.push(root.val)
if(!root.left && !root.right && newSum === 0){
res.push(path.slice())
}
findPath(root.left,newSum,path)
findPath(root.right,newSum,path)
}
findPath(root,sum,[])
path.pop() // 回溯原因，因为函数传值与传址区别，所以findPath的path都是指向一个地址
return res;
}
为什么要用回溯？
关键是函数传值与传址区别，导致每次findPath的path都是同一个
如下面二叉树，如果目标路径和8，最终得到的结果却是【1，2，4，5】
正确的应该是【1，2，5】
因为findPath(2.left,7,[1]) //以后path变成了[1,2,4]
接着findPath(2.right,7,[1,2,4]) // 这里的path由于都是指向同一个，所以变成了【1，2，4】本来应该【1，2】
如果不回溯，下面就后出现
1
/ \
2 3
/ \
4 5
