1. 题目描述

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

2. 思路分析

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

3. 代码实现

/**
 * 二叉树结点类
 */
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));
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