2

所以，问题是在 BST 的二叉树中找到最大的子树（最大的子树是具有最大大小的节点）。

我找到了以下包含算法的网站。

http://amazoninterview.blogspot.in/2011/10/find-largest-binary-search-tree-in.html

现在重复执行上述代码，我发现它给出了正确的结果。然而，我发现（通过空运行和直觉）而不是它分配的位置（int函数getmaxbst（），

subtreemin = leftsubtreemin;
subtreemax = rightsubtreemax;

它应该执行以下操作

subtreemin = leftsubtreemax;
subtreemax = rightsubtreemin;

我尝试使用上述更改执行代码，它提供了相同且正确的结果。

有人可以帮我找出上述哪个作业是正确的以及为什么

4

1 回答 1

0

原始算法分配是正确的。

'subtreemin' 和 'subtreemax' 是 'getmaxbst' 函数的参数，通过引用传递。当这些变量被赋值时，它也改变了传递给函数的变量，它要么是leftsubtree min/max，要么是rightsubtree min/max。由于在分配点已经确定子树实际上是 BST，因此树的最小值将是左子树的最小值（即 leftsubtreemin），而树的最大值将是最大的右子树的值（rightsubtreemax）。

我相信你的错误在于认为'subtreemin'和'subtreemax'被用作比较以确定子树是否实际上是BST，但是此时这是用不同的变量（即leftsubtreemax和rightsubtreemin）完成的

if(root->data < leftsubtreemax ||
 root->data > rightsubtreemin){
return -1;

至于为什么两者都产生相似且正确的结果，我无法在不查看数据的情况下告诉您，但是更改分配似乎会产生错误的结果。您可能对某些测试用例很幸运。

于 2013-07-08T20:25:26.120 回答