剑指 Offer 34. 二叉树中和为某一值的路径(中等)

通过率 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 };

 

剑指 Offer 34. 二叉树中和为某一值的路径(中等)

上一篇:软件7大设计原则


下一篇:Julia ---- 随机数字/数组 和 数字转字符串