☰

Javaでツリー内のノードを数える 質問する

tag-icon • tag-icon java recursion tree
Javaでツリー内のノードを数える 質問する

まず最初に、これは宿題ではなく、面接で聞かれた質問だと断言します。私はうまく答えられなかったと思います (ただし、解決には再帰が必要であることは認識していました)。質問は次のとおりです。

ツリー内のノードの数を返すcount()メソッドを実装します。ノードに左または右の子がない場合、関連するgetXXChild()メソッドは以下を返します。null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

私がこの質問をした理由は、単に正しい解決策を知り、それによって自分の解決策がどれだけひどかったかを測りたいと思ったからです。

乾杯、トニー

ベストアンサー1

int count() {
  Tree right = getRightChild();
  Tree left = getLeftChild();
  int c = 1;                                      // count yourself!
  if ( right != null ) c += right.count();        // count sub trees
  if ( left != null ) c += left.count();          // ..
  return c;
}

おすすめ記事