通过率 57.8%
题目描述:
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 target = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
节点总数 <= 10000
思路：
深搜，有两个注意点：
- 不要直接将路径path追加到res中，否则加入的只是path的内存地址，后面path变了res里所存的路径也会跟着变，正确做法是先对path进行深拷贝，然后将深拷贝出来的新数组追加到res中
- 对于空树，直接返回空数组
1 /*JavaScript*/ 2 /** 3 * Definition for a binary tree node. 4 * function TreeNode(val, left, right) { 5 * this.val = (val===undefined ? 0 : val) 6 * this.left = (left===undefined ? null : left) 7 * this.right = (right===undefined ? null : right) 8 * } 9 */ 10 /** 11 * @param {TreeNode} root 12 * @param {number} target 13 * @return {number[][]} 14 */ 15 // 深搜 16 var dfs = function(node, target, path, sum, res) { 17 path.push(node.val) 18 sum += node.val 19 // 叶节点 20 if(!node.left && !node.right) { 21 if(sum === target) { 22 // 对path进行深拷贝并追加到res中 23 const temp = [] 24 path.forEach(item => { 25 temp.push(item) 26 }) 27 res.push(temp) 28 } 29 return path.pop() 30 } 31 if(node.left) dfs(node.left, target, path, sum, res) 32 if(node.right) dfs(node.right, target, path, sum, res) 33 path.pop(node.val) 34 } 35 36 var pathSum = function(root, target) { 37 if(!root) return [] 38 const res = [] 39 dfs(root, target, [], 0, res) 40 return res 41 };