檢查樹是否有0個或2個孩子

Question

如何檢查整棵樹是否半完美有0個或2個節點？考慮以下情況：

• 有0個孩子的節點是半完美的。
• 有1個孩子的節點不是半完美的。
• 帶2個孩子的節點是半完美的，如果 （尺寸的，較大的孩子< =尺寸的，較小的孩子* 3）

這是我到目前爲止有：

public static boolean isLeafOrHasTwoChildren(Node t) { 
    if (t.left == null && t.right == null) { 
     return true; 
    } 

    if (t.left == null || t.right == null) { 
     return false; 
    } 
    // Recurse down the tree 
    return isLeafOrHasTwoChildren(t.left) 
     && isLeafOrHasTwoChildren(t.right); 
} 

大小計算樹中節點的數量。

Answer 1

讓我們列舉一下我們的條件。

• 如果所有訪問節點都爲空，則返回true。
• 如果定義了所有訪問的節點，則返回true。
• 否則返回false。

讓我們確定的第一個條件 - isLeaf - 如：

boolean isLeaf = t.left == null && t.right == null; 

讓我們來定義hasAllChildren爲：

boolean hasAllChildren = !(t.left == null || t.right == null); 

如果我們仔細觀察，!(t.left == null || t.right == null)相同t.left == null && t.right != null由於德摩根定律。這使我們能夠相當直接地表達這一點，而這可能就是你錯過的一塊。

現在，我們來討論遞歸流。我們希望以訪問左右方式走下整個節點鏈。所以，我們想在檢查之前檢查我們的條件。基本案例：如果我們不是葉子（意味着我們沒有所有的孩子），我們立即返回假。

遞歸步驟：如果我們是葉子或者我們有所有的孩子，我們繼續下去。

讓我們試着表達這一點。

public static boolean isLeafOrHasTwoChildren(Node t) { 
    // Trivial case; if we have an undefined node, we've definitely reached a leaf. 
    if (t == null) { 
     return true; 
    } 

    boolean isLeaf = t.left == null && t.right == null; 
    boolean hasAllChildren = !(t.left == null || t.right == null); 

    if(isLeaf || hasAllChildren) { 
     return isLeafOrHasTwoChildren(t.left) && isLeafOrHasTwoChildren(t.right); 
    } else { 
     return false; 
    } 
}