题目:
难度:Middle
相关话题:树
、深度优先搜索
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树,以及目标和 sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
思路:
必须同时满足sum
和leaf
节点,才能作为结果添加进res
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var pathSum = function(root, sum) {
let res=[]
function dfs(root,sum,arr){
if(!root)return
if(sum===root.val && !root.left && !root.right){
arr.push(root.val)
res.push(arr.slice())
arr.pop()
return
}
arr.push(root.val)
dfs(root.left,sum-root.val,arr)
dfs(root.right,sum-root.val,arr)
arr.pop()
}
dfs(root,sum,[])
return res
};