Open
Description
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
典型的可以用 DFS 来解决的问题,定义一个 search 方法并且参数里带一个用来收集路径的 paths 数组,每当到达叶子节点(没有 left 也没有 right),就计算一把路径的总和,如果等于目标值就 push 到结果数组里。(注意这里要浅拷贝一下,防止下面的计算污染这个数组)
任何一个节点处理完成时,都要把当前节点 pop 出 paths 数组。
let pathSum = function (root, sum) {
let res = [];
let search = function (node, paths) {
if (isInvalid(node)) return;
paths.push(node.val);
if (node.left) {
search(node.left, paths);
}
if (node.right) {
search(node.right, paths);
}
if (!node.left && !node.right) {
if (sumVals(paths) === sum) {
res.push(paths.slice());
}
}
paths.pop();
};
search(root, []);
return res;
};
function sumVals(nodes) {
return nodes.reduce((prev, val) => {
prev += val;
return prev;
}, 0);
}
function isInvalid(node) {
return !node || node.val === undefined || node.val === null;
}