1. 题目描述

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

2. 思路分析

  1. 每次来到新的节点，记录新节点信息
  2. 检查新节点是否是叶子节点，如果是，判断路径上的节点值总和是否符合条件；如果不是，继续递归处理左右子树，回到第 1 步
  3. 最后需要将新节点的信息移除

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 二叉树结点类
 */
class Node {
    constructor(value = 0, left = null, right = null) {
        this.value = value
        this.left = left
        this.right = right
    }
}

/**
 *
 * @param {Node} root
 * @param {Number} target
 */
function findPath(root, target) {
    const paths = [] // 存放所有满足条件的路径
    let sum = 0 // 路径上的节点值的总和

    function _findPath(node, path) {
        if (node === null) {
            return
        }

        // 把当前节点放入路径中
        sum = sum + node.value
        path.push(node)

        const isLeaf = node.left === null && node.right === null

        // 如果是叶节点, 并且路径上的节点和满足条件, 记录这条路径
        if (isLeaf && sum === target) {
            paths.push([...path])
        }

        // 当前节点有左子树, 向左子树递归
        if (node.left !== null) {
            _findPath(node.left, path)
        }

        // 当前节点有右子树, 向右子树递归
        if (node.right !== null) {
            _findPath(node.right, path)
        }

        // 把当前节点从路径中移除
        sum = sum - node.value
        path.pop(node)
    }

    _findPath(root, [])
    return paths
}

/**
 * 以下是测试代码
 */
const root = new Node(1, new Node(2), new Node(3, null, new Node(-1)))

console.log(findPath(root, 3))