java - 二分探索木で子が2つあるノードの数を数える方法

Question

それは私が思いつくことができる最高のものですが、2つの子を持つノードが複数あった場合でも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

欠けている小さなものが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

ルートに左右両方のノードがある場合、プログラムは最初に終了するため、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 3

ノードにnullではない左と右の両方のリンクがあるかどうかをチェックするifステートメントがあるように、不足しているのはelseだけですが、nullの場合はどうなりますか?

あなたは単純にelseを追加することができます:

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

また、左ノードと右ノードの両方が null でない場合は 1 を返すだけだと言ったときに、間違っていました。左ノードと右ノードのそれぞれに対して countTwoChildren を再帰的に呼び出して、ツリーを走査し続けて他のノードを見つける必要があります。

Answer 4

問題は、ノードに 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;
}

もちろん、このすべてを 1 行で記述できます。

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

Answer 5

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;
}