社区首页 >问答首页 >两个BST叶之间的节点总和

问两个BST叶之间的节点总和
EN

Stack Overflow用户

提问于 2019-09-14 23:07:31

回答 1查看 141关注 0票数 0

我不是在寻找树的最大和路径。我可以创建并找到二叉树的总和，但我需要找到两个叶子之间所有节点的总和。

例如，对于使用以下节点构建的BST :5、10、13、8、3、4、5，树如下所示：

                         5
                     /       \
                   3           10
                    \         /  \
                     4       8    13
                            /
                           5

因此，如果输入为4和13，则节点的总和为3+5+10=18。

函数可能是这样的：Sum(tree, firstNumber, secondNumber);

我正在考虑创建两个有序列表，其中包含直到根节点的所有节点，并查看它们中是否有公共节点，然后将所有唯一节点的值相加。它在时间复杂度和内存管理方面都很糟糕，所以我想看看有没有更简单的方法

编辑: M. Hazara是对的，5不是叶子。所以我删除了这个例子

algorithm

tree

binary-search-tree

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-09-15 02:52:52

嗯，可能首先想到的想法是为两个叶子的每个节点列出一个列表。然而，由于它是二进制搜索树(BST)，采用哪条路径的条件是已知的，因此可以跟踪哪些节点在公共路径中，哪些节点不在公共路径中。

首先，BST搜索总是从根节点开始，因此它始终是和的一部分，假设BST有3个或更多节点，因为我们需要两个leafs。其次，有必要对每个叶(firstNumber，secondNumber)执行BST搜索，以确保我们遍历了每条路径的节点，而不管它们是否通用。最后，剩下的就是确定节点在两条路径中何时是公共的，这样我们就不会两次添加相同的值。

如果两个BST搜索采用相同的路径，则节点位于公共路径中。所以，你必须在你的函数中同时运行这两个函数。我们可以使用do-while来计算总和中的所有公共节点：

firstCurrentNode = tree.Root;
secondCurrentNode = tree.Root;
do {
  sum += firstCurrentNode;
  // FirstNumber path check:
  if (firstNumber < firstCurrentNode) firstCurrentNode = firstCurrentNode.goLeftNode();
  else firstCurrentNode = firstCurrentNode.goRightNode();
  // SecondNumber path check:
  if (secondNumber < secondCurrentNod) secondCurrentNode = secondCurrentNode.goLeftNode(); 
  else secondCurrentNode = secondCurrentNode.goRightNode(); 
} while (firstCurrentNode == secondCurrentNode)

一旦它们不相等，即采取不同的路径，由于树的属性，它们将永远不会再共享相同的路径。因此，我们只需要单独地继续BST搜索，包括我们找到的每个节点的总和。然而，我们可能已经到达了leafs，所以有必要首先检查一下：

// Search for firstNumber
while(firstCurrentNode != firstNumber) {
  sum += firstCurrentNode;
  if (firstNumber < firstCurrentNode) firstCurrentNode = firstCurrentNode.goLeftNode();
  else firstCurrentNode = firstCurrentNode.goRightNode();
}
// Search for secondNumber
while(secondCurrentNode != secondNumber) {
  sum += secondCurrentNode;
  if (secondNumber < secondCurrentNod) secondCurrentNode = secondCurrentNode.goLeftNode(); 
  else secondCurrentNode = secondCurrentNode.goRightNode();
}