二叉树中和为某一值的路径

前言

有一颗二叉树和一个整数，如何找到二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。本文就跟大家分享下这个问题与解决方案，欢迎各位感兴趣的开发者阅读本文。

思路分析

我们举例来做分析，如下图所示，我们准备了一颗二叉树和一个整数22，通过观察后，我们很容易就能看出它有两条路径的节点值加起来和为22。

• 10、5、7
• 10、12

                                 image-20221031215401500

上述两个路径都是从根节点出发到叶子节点的，也就是说路径总是以根节点为起始点，因此我们首先需要遍历根节点。在树的三种遍历方式中，只有前序遍历是首先访问根节点的。

按照前序遍历的顺序去访问这颗二叉树，在访问节点10之后，就会访问节点5。图中二叉树并没有指向父节点的指针，当访问节点5的时候，我们是不知道前面经过了哪些节点的，此时我们就需要准备一个栈，用来存储访问过的节点。

当到达节点5的时候，路径中包含两个节点：10、5。接下来遍历到节点4，我们把这个节点入栈，这时候已经到达叶节点，但栈中的所有节点之和是19。这个和不等于输入的值22，因此它不符合要求的路径。

最后，我们要遍历的节点是12。在遍历这个节点之前，需要先经过节点5回到节点10。同样的，每次当从子节点回到父节点的时候，我们都需要在路径上删除子节点。最后在节点10到达节点12的时候，路径上的两个节点的值之和也是22，因此这也是一条符合要求的路径。

分析到这里，我们就找到了一些规律：

• 当用前序遍历的方式访问到某一节点时，就把该节点添加到路径上，并累加该节点的值
• 如果该节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则当前路径符合要求
• 如果该节点非叶节点，则继续访问它的子节点。从节点路径栈中删除当前节点
• 递归上述过程，直至二叉树的所有节点访问完毕。

                         image-20221106171157024  

实现代码

形成了清晰的思路之后，接下来我们就可以轻松的写出代码了，如下所示：

• 声明需要的变量：已访问过的路径栈、满足预期的路径数组、当前已访问节点的值总和
• 从root节点开始，用前序遍历访问所有节点，筛选并存储满足预期条件的路径

findPath(root: Node<number>, expectedSum: number): Array<string> {
    if (root == null) return [];
    // 用一个栈来存储访问过的路径
    const pathStack = new Stack();
    // 存储符合条件的路径
    const pathList: Array<string> = [];
    // 当前已访问路径总和
    const currentSum = 0;
    // 从root节点开始搜索节点
    this.searchNode(root, expectedSum, pathStack, currentSum, pathList);
    return pathList;
  }

• 取出根节点的值，将其进行累加
• 累加后，将根节点的值压入路径栈中
• 判断是否访问到了叶节点，如果为叶节点且当前已访问的节点路径总和等于预期条件则将路径栈中的路径放入符合条件的路径数组中
• 当前节点非叶节点，则继续递归访问它的左、右子树
• 左、右子树都访问完成后，则代表当前路径不满足预期条件，将其从路径栈中出栈

private searchNode(
    root: Node<number>,
    expectedSum: number,
    pathStack: Stack,
    currentSum: number,
    pathList: Array<string>
  ) {
    // 累加当前已访问节点的和，将当前节点入栈
    currentSum += root.key;
    pathStack.push(root.key);
    // 如果是叶节点，并且路径上节点值的和等于输入的值，则存储当前路径栈中的节点
    const isLeaf = root.left == null && root.right == null;
    if (currentSum == expectedSum && isLeaf) {
      pathList.push(pathStack.toString());
    }
    // 非叶子节点，则遍历它的子节点
    if (root.left != null) {
      this.searchNode(root.left, expectedSum, pathStack, currentSum, pathList);
    }
    if (root.right != null) {
      this.searchNode(root.right, expectedSum, pathStack, currentSum, pathList);
    }
    // 当前节点不符合条件，将其出栈
    pathStack.pop();
  }

测试用例

接下来我们用文章开头的例子来测试下上述代码能否正确执行。

const tree: Node<number> = {
  key: 10,
  left: {
    key: 5,
    left: {
      key: 4
    },
    right: {
      key: 7
    }
  },
  right: {
    key: 12
  }
};
const targetVal = 22;
const resultPath = treeOperateTest.findPath(tree, targetVal);
console.log(resultPath);

如下所示，成功得计算出了两条路径。

                        image-20221106172940751

我们将节点12改成20，再来测试下，结果如下所示，只有一条路径符合预期。

                           image-20221106173156898

示例代码

本文用到的代码完整版请移步：

• TreeOperate.ts
• TreeOperate-test.ts

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

如果你对我感兴趣，请移步我的个人网站，进一步了解。

• 公众号无法外链，如果文中有链接，可点击下方阅读原文查看😊