- Notifications
You must be signed in to change notification settings - Fork45
Open
Description
仰望星空的人，不应该被嘲笑
题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和sum=22，5/ \48//\11134/ \/\7251
返回:
[[5,4,11,2],[5,8,4,5]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
dfs，进行深度优先遍历，一直遍历到子节点为止，进行一次判断，如果当前sum为 0 ，那么就是我们想要的结果，然后注意js 语法中形参如果是数组，那么我们拿到的是引用值，可以拷贝一份。
/** * 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[][]} */varpathSum=function(root,sum){if(!root)return[];letres=[];letdfs=(cur,root,sum)=>{if(root==null)return0;// 拷贝一份cur=[...cur,root.val];sum-=root.val;if(!root.left&&!root.right&&sum==0){res.push(cur);return;}// 优先遍历左子树root.left&&dfs(cur,root.left,sum);root.right&&dfs(cur,root.right,sum);}dfs([],root,sum);returnres;};
不太明白的小伙伴，这里给一个友好的提示，我们可以打印一下拷贝出来的cur，结合图示应该就好理解了，经典的dfs实现的先序遍历。
5/ \48//\11134/ \/\7251
[5][5,4][5,4,11][5,4,11,7][5,4,11,2][5,8][5,8,13][5,8,4][5,8,4,5][5,8,4,1]
最后
文章产出不易，还望各位小伙伴们支持一波！
往期精选：
leetcode-javascript：LeetCode 力扣的 JavaScript 解题仓库，前端刷题路线（思维导图）
小伙伴们可以在Issues中提交自己的解题代码，🤝 欢迎Contributing，可打卡刷题，Give a ⭐️ if this project helped you!
访问超逸の博客，方便小伙伴阅读玩耍~
学如逆水行舟，不进则退