java - 一种计算二叉搜索树中具有 2 个子节点的节点数的方法

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

好吧，您缺少的只是一个 else，就像您有一个 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;
}