遞歸在java和跨棧保持變量狀態

我試圖在BST這裏的問題是「檢查是否所有葉子都在同一級別」遞歸在java和跨棧保持變量狀態

在這個問題解決一個問題，我需要保持遞增每個堆棧調用級別，但也保持所有調用的最大值。除此之外，我需要返回一個結果的布爾值。

這是很簡單的解決，我需要繼續做下來的樹，我這樣做

int maxlevel = 0; 
public boolean allAtSameLevel(Node root, int level){ 
    if(root== null){ 
     return false; 
    } 
    if(root.left== null && root.right == null){ 
     if(maxlevel == 0){ 
      maxlevel = level; 
     } 
     return(level== maxlevel); 
    } 
    return allAtSameLevel(root.left, level+1) && allAtSameLevel(root.right, level+1) ; 
}

我的問題是，對於需要共享的價值，我必須保持一個實例變量在Java中。有一個更好的方法嗎？我的困惑是，既然它會一直走到右邊的葉子，然後上升，通過價值將無濟於事。有任何想法嗎？

來源

2014-05-23 12rad

訣竅是將子樹的深度傳遞迴堆棧的更高層，但只有在右側和左側深度都相同的情況下才會這樣做。你可以用一個簡單的遞歸函數做到這一點：

int eqDepth(Node n) { 
    if (n == null) return 0;  // This is a leaf, its subtree depth is zero 
    int dLeft = eqDepth(n.left); // Make two recursive calls 
    int dRight = eqDepth(n.right); 
    // If one of the depths is negative, or the depths are different, 
    // report it by returning negative 1: 
    if (dLeft < 0 || dRight < 0 || dLeft != dRight) return -1; 
    return 1+dLeft; // It's the same as dRight 
}

有了這些功能，您可以在一個線路編碼allAtSameLevel：

public boolean allAtSameLevel(Node root) { 
    return eqDepth(root) >= 0; 
}

這裏是一個demo on ideone.一開始是一個不平衡的樹，得到了-1

 a 
/ \ 
    b  c 
/\ /\ 
d e f -

然後添加缺少的節點

 a 
/ \ 
    b  c 
/\ /\ 
d e f g

並得到肯定的結果。

來源

2014-05-23 19:48:03 dasblinkenlight

謝謝你的回答。但我認爲這個解決方案是比較每個根的左邊和右邊，並返回值而不是整個樹的葉節點。我測試了它，只要根有兩個孩子，它就會返回大於等於0的值。 – 12rad

@ 12rad糟糕，我忘了在先前調用的結果中添加一個。它現在有效 - 看看演示。 – dasblinkenlight

雅，那工作。因此，您不必下調計算級別，而是採取自下而上的方式來返回值並添加並進行比較。我想我需要多練習！但是，謝謝。 – 12rad

遞歸在java和跨棧保持變量狀態

回答

相關問題