一種方法來計算在二進制搜索樹中有兩個孩子的節點數

Question

這就是最好的我可以上來，但它仍然無法正常工作因爲它返回1即使有多個節點有兩個孩子。

int countTwoChildren(Node node) 
{ 
    if(node==null) { 
     return 0; 
    } 
    if(node.left!=null && node.right!=null) { 
     return 1; 
    } 
    return countTwoChildren(node.left) + countTwoChildren(node.right); 
} 

任何人都可以在上面的一段代碼中找到任何錯誤？

Answer 1

一件小事缺失：

int countTwoChildren(Node node) 
{ 
    if(node==null) { 
     return 0; 
    } 
    if(node.left!=null && node.right!=null) { 
     return 1 + countTwoChildren(node.left) + countTwoChildren(node.right); 
    } 
    return countTwoChildren(node.left) + countTwoChildren(node.right); 
} 

Answer 2

你的問題是，如果一個節點有兩個孩子，你不向下降落了自己的孩子。你應該改變的檢查順序：

int countTwoChildren(Node node) 
{ 
    int nc; 

    if(node==null) { 
     return 0; 
    } 

    nc = countTwoChildren(node.left) + countTwoChildren(node.right); 
    if(node.left!=null && node.right!=null) { 
     return nc++; 
    } 

    return nc; 
} 

當然，所有這一切都可以寫在一行：

int countTwoChildren(Node node) 
{ 
    return (node == null 
      ? 0 
      : countTwoChildren(node.left) + countTwoChildren(node.right) + 
       (node.left!=null && node.right!=null ? 1 : 0)); 
} 

Answer 3

int countTwoChildren(Node node) 
{ 
    if (node == null) 
     return 0; 
    int here = node.left != null && node.right != null ? 1 : 0; 
    int left = countTwoChildren(node.left); 
    int right = countTwoChildren(node.right); 
    return here + left + right; 
} 

Answer 4

那麼你所有的缺失是一個意外，就像你有一個if語句來檢查，如果該節點已離開兩者右&鏈接不爲空，但如果它是空的東西，

你可以簡單地添加其他：

if(node.left!=null && node.right!=null) { 
    return 1 + countTwoChildren(node.left) + countTwoChildren(node.right); 
}else{ 
    return countTwoChildren(node.left) + countTwoChildren(node.right); 
    } 

此外，當你說如果左右節點都不爲空，它將返回1，你應該繼續遍歷樹找到另一個通過遞歸調用左側節點的countTwoChildren和右側節點。

Answer 5

如果root擁有左右節點，程序將首次終止，因此它將返回1，並且不會進行遞歸調用。這裏是解決方案，希望它有助於

public static int numberOfFullNode(TreeDemo root){ 
     if(root==null) 
      return 0; 
     else if(root.left!=null && root.right!=null) 
      return 1+numberOfFullNode(root.left)+numberOfFullNode(root.right); 
     else return 0; 
    } 

Answer 6

的問題已經回答得很好，只是分擔了同樣的問題迭代求解：

public static int findTheNumberOfFullNodesIterative(BTNode root) { 

    int noOfFullNodes = 0; 
    if (root == null) { 
     return 0; 
    } 
    Queue<BTNode> q = new LinkedList<>(); 
    q.offer(root); 

    while (!q.isEmpty()) { 
     BTNode temp = q.poll(); 
     if (temp.getLeft() != null && temp.getRight() != null) { 
      noOfFullNodes++; 

     } 
     if (temp.getLeft() != null) { 
      q.offer(temp.getLeft()); 
     } 
     if (temp.getRight() != null) { 
      q.offer(temp.getRight()); 
     } 
    } 
    return noOfFullNodes; 
}