二叉树中和为某一值的路径(二) - js
程序员文章站
2022-05-18 16:54:57
...
二叉树中和为某一值的路径(二) - JS
描述
输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点,不能从子节点到父节点
4.总节点数目为n
输入:
{10,5,12,4,7},22
返回值:
[[10,5,7],[10,12]]
说明:返回[[10,12],[10,5,7]]也是对的
思路:
1.两个数组,一个result数组保存全部符合要求的路径。一个数组path保存单条符合路径的节点数据。
2.最后递归左右子树遍历全部节点,只要加和等于题目要求就创建一个新的数组,将path中的数据复制给新数组,再将新数组放到result数组中去。
代码实现:
function FindPath(root, expectNumber)
{
// write code here
let result = []
let path = []
function pathFound(root,target,count){
if(root == null) return
// 节点一进来就加和 并且将节点数据放到路径数组中
count += root.val
path.push(root.val)
if(target == count && root.left == null && root.right == null){
// 加和符合条件的前提下当前这个节点必须是叶子节点
// 同时满足这两个条件 创建新数组 并且将新的数组放进结果数组中
result.push([...path])
}
pathFound(root.left,target,count)
pathFound(root.right,target,count)
// 没彻底执行完一次函数 就将数组中的最后一个数据弹出
// 保持数组中的数据实时更新 才能在符合条件的时候直接赋值给新数组,并且压入结果数组
path.pop()
}
pathFound(root,expectNumber,0)
return result
}