路径总和(从根节点出发)
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
// 解题思路:
路径: 根节点-> 叶子节点
其中叶子节点没有子节点
var pathSum = function(root, targetSum) {
let ret = []
const isValid = (node,sum) => {
if (sum!=targetSum) return false
if (node.left || node.right) return false
return true
}
const dfs = (node,sum,path=[]) => {
if(!node) return
let _sum = sum + node.val
if(isValid(node,_sum)) {
path.push(node.val)
ret.push(path)
return
}
if(node.left) dfs(node.left, _sum, [...path, node.val])
if(node.right) dfs(node.right, _sum, [...path, node.val])
}
dfs(root,0)
return ret
};
路径总和(从任意节点出发)
输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
// 解题思路:
// 1.遍历树,以每个节点为起始点;
// 2.因为存在后面子节点值之和等于0;故isVaild(_sum)满足条件后,需要继续遍历;
var pathSum = function(root, targetSum) {
let ret = 0;
const isVaild = (sum) => {
return sum == targetSum
}
const dfs = (node, sum) => {
if(!node) return
let _sum = node.val + sum
if(isVaild(_sum)) ret++
dfs(node.left, _sum)
dfs(node.right, _sum)
}
// 遍历树,以每个节点为起始点
const dfsTree = (node) => {
if(!node) return
dfs(node, 0)
dfsTree(node.left, 0)
dfsTree(node.right, 0)
}
dfsTree(root)
return ret
};