java - 在Java中计算树中的节点

Question

首先，我发誓这不是作业，这是我在一次采访中被问到的问题。我想我把它弄得一团糟(尽管我确实意识到解决方案需要递归)。问题来了:

实现 count() 方法，该方法返回树中的节点数。如果一个节点既没有左 child 也没有右 child ，相关的 getXXChild() 方法将返回 null

class Tree {

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

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

  int count() {
    // Implement me
  }
}

我问这个问题的原因只是想看看正确的解决方案，从而衡量我的问题有多糟糕。

干杯，托尼

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