2016-02-28 54 views
2

我目前正在嘗試實現一個二叉搜索樹形狀比較,並且遇到了我的一行代碼的問題。你如何通過兩個返回語句遞歸? [JAVA]

if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal! 
    { 
     return true; 
    } 
    if(treeStructOne.getHeight() != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal 
    { 
     return false; 
    } 
     if(treeStructOne.hasLeft() && treeStructTwo.hasLeft()) 
     { 
      return similar(treeStructOne.getLeft(),treeStructTwo.getLeft()); 

     } 
     if(treeStructOne.hasRight() && treeStructTwo.hasRight()) //PROBLEM IS HERE 
     { 
      return similar(treeStructOne.getRight(),treeStructTwo.getRight()); 
     }   
     return false; 

出現該問題時,在樹1和2中的節點有左子,但只有1樹擁有權利,而不是樹2後,它會檢查他們都已經離開了孩子,這不運行正確的孩子檢查,如果離開是真的。這是用java的遞歸方式嗎?

+0

它在幾乎任何可以想象的命令式語言中以這種方式工作。當你回來時,你會回來。沒有更多的是執行。 –

回答

4

如果兩個樹hasLeft()返回true,那麼您的方法將返回該if子句。我的猜測是你要的結果從類似的呼籲在過去的兩年,如果從句分配和if語句後這樣做

return leftSimilar && rightSimilar; 
2

前兩個,如果公司將工作,但最後一部分應該捕獲的條件p暗示q對於左右都是〜p或q。換句話說,如果treeStructOne有一個左子樹和treeStructTwo有左子樹,然後檢查,看看他們是相似的(返回類似...)

if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal! 
    { 
     return true; 
    } 
if(treeStructOne.getHeight() != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal 
    { 
     return false; 
    } 
return (treeStructOne.hasLeft() && treeStructTwo.hasLeft() 
     ? similar(treeStructOne.getLeft(),treeStructTwo.getLeft()) 
     : false) 
    && (treeStructOne.hasRight() && treeStructTwo.hasRight() 
     ? similar(treeStructOne.getRight(),treeStructTwo.getRight()) 
     : false); 
+1

仍然看起來不對。如果一個人只有離開而另一個只有對的人,它會返回true。 –

+0

道歉的錯字。我在想你說的是什麼。你可能是對的... –

+0

@SergeyTachenov我認爲你對這些案件是正確的,是的,這可以存儲在變量,但條件表達式似乎是正確的。 –

0

return語句,將立即從目前的方法,即返回該方法的其餘部分將不會執行。

在你的情況下,你想在從方法返回之前進行兩次遞歸調用。

boolean similarLeft; 
if(treeStructOne.hasLeft() && treeStructTwo.hasLeft()) { 
    similarLeft = similar(treeStructOne.getLeft(),treeStructTwo.getLeft()); 
} else { 
    similarLeft = ?; // TODO what is good condition here? 
} 

然後做同樣的右側,並與

return similarLeft && similarRight; 

斷定然而,對於真正ideomatic java的,我會做null檢查調用方法,而之後:您可以做到這一點然後在它之前,從而減少代碼重複:

boolean similar(TreeStruct x, TreeStruct y) { 
    if (x == null) { 
     return y == null; 
    } else { 
     return y != null && similar(x.left, y.left) && similar(x.right, y.right); 
    } 
}