有一颗二叉树和一个整数,如何找到二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。本文就跟大家分享下这个问题与解决方案,欢迎各位感兴趣的开发者阅读本文。
我们举例来做分析,如下图所示,我们准备了一颗二叉树和一个整数22,通过观察后,我们很容易就能看出它有两条路径的节点值加起来和为22。
image-20221031215401500
上述两个路径都是从根节点出发到叶子节点的,也就是说路径总是以根节点为起始点,因此我们首先需要遍历根节点。在树的三种遍历方式中,只有前序遍历是首先访问根节点的。
按照前序遍历的顺序去访问这颗二叉树,在访问节点10之后,就会访问节点5。图中二叉树并没有指向父节点的指针,当访问节点5的时候,我们是不知道前面经过了哪些节点的,此时我们就需要准备一个栈,用来存储访问过的节点。
当到达节点5的时候,路径中包含两个节点:10、5。接下来遍历到节点4,我们把这个节点入栈,这时候已经到达叶节点,但栈中的所有节点之和是19。这个和不等于输入的值22,因此它不符合要求的路径。
最后,我们要遍历的节点是12。在遍历这个节点之前,需要先经过节点5回到节点10。同样的,每次当从子节点回到父节点的时候,我们都需要在路径上删除子节点。最后在节点10到达节点12的时候,路径上的两个节点的值之和也是22,因此这也是一条符合要求的路径。
分析到这里,我们就找到了一些规律:
image-20221106171157024
形成了清晰的思路之后,接下来我们就可以轻松的写出代码了,如下所示:
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
本文用到的代码完整版请移步:
至此,文章就分享完毕了。
我是神奇的程序员,一位前端开发工程师。
如果你对我感兴趣,请移步我的个人网站,进一步了解。