二叉樹中最大的二叉樹搜索樹

Question

因此，問題是在二叉樹中找到最大的子樹（最大的子樹是最大尺寸的節點），它是BST的二叉樹。

我發現了下面的網站，它列出了一個算法。

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

現在在上述代碼的重複執行，我發現，它給了正確的結果。不過，我覺得（通過幹運行和直覺），與其在那裏分配（INT功能getmaxbst（），

subtreemin = leftsubtreemin; 
subtreemax = rightsubtreemax; 

它應該做到以下幾點

subtreemin = leftsubtreemax; 
subtreemax = rightsubtreemin; 

我試圖執行代碼上述變化和它提供的相同和正確的結果。

誰能幫我找到了上述轉讓這是正確的，爲什麼

Answer 1

的原廠l算法分配是正確的。

'subtreemin'和'subtreemax'是'getmaxbst'函數的參數，並通過引用傳遞。當這些變量被分配給它時，它也會改變傳遞給函數的變量，它是leftsubtree min/max或者rightsubtree min/max。由於在分配點已經確定子樹實際上是BST的，所以樹的最小值將是左子樹的最小值（其爲左半子樹），並且樹的最大值將是最大的右子樹的值（rightsubtreemax）。

我相信你的錯誤在於認爲'subtreemin'和'subtreemax'被用作比較來確定子樹是否實際上是BST，但是這是在不同的變量（即leftsubtreemax和rightsubtreemin）下完成的點

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

至於爲何兩者都生產相似，正確的結果我不能告訴你，不看數據，但它似乎改變分配會產生錯誤的結果。您可能會遇到某些測試用例。