在Java中计算树中的节点

Question

首先,我发誓这不是家庭作业,这是我在接受采访时被问到的一个问题.我想我弄得一团糟(尽管我确实意识到解决方案需要递归).这是一个问题:

实现count()方法,该方法返回树中的节点数.如果节点没有左子节点或右子节点,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;
}

Answer 2

一个简单的递归解决方案:

int count() {
   Tree l = getLeftTree();
   Tree r = getRightTree();
   return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}

一个不那么琐碎的非递归的:

int count() {
    Stack<Tree> s = new Stack<Tree>();
    s.push(this);
    int cnt = 0;
    while (!s.empty()) {
        Tree t = s.pop();
        cnt++;
        Tree ch = getLeftTree();
        if (ch != null) s.push(ch); 
        ch = getRightTree();
        if (ch != null) s.push(ch); 
    }
    return cnt;
}

后者可能稍微提高内存效率,因为它用堆栈和迭代替换递归.它也可能更快,但没有测量就很难分辨.一个关键的区别是递归解决方案使用堆栈,而非递归解决方案使用堆来存储节点.

编辑:这是迭代解决方案的一种变体,它使用堆栈的次数较少:

int count() {
    Tree t = this;
    Stack<Tree> s = new Stack<Tree>();
    int cnt = 0;
    do {
        cnt++;
        Tree l = t.getLeftTree();
        Tree r = t.getRightTree();
        if (l != null) {
            t = l;
            if (r != null) s.push(r);
        } else if (r != null) {
            t = r;
        } else {
            t = s.empty() ? null : s.pop();
        }
    } while (t != null);
    return cnt;
}

无论您需要更高效还是更优雅的解决方案,自然取决于树木的大小以及您打算使用此例程的频率.Rembemer Hoare说道:"过早优化是万恶之源."

Answer 3

我更喜欢这个,因为它写道:

返回计数为左+计数为rigth + 1

  int count() {
      return  countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
  }
  private int countFor( Tree tree )  { 
       return tree == null ? 0 : tree.count();
  }

更多的文字编程.

顺便说一句,我不喜欢Java上常用的getter/setter约定,我认为使用leftChild()会更好:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1;

就像Hoshua Bloch在这里解释http://www.youtube.com/watch?v=aAb7hSCtvGw一样.32:03

如果你得到它,你的代码会读取...

但是,我必须承认get/set约定现在几乎是该语言的一部分.:)

对于许多其他部分,遵循此策略创建自我记录代码,这是好事.

托尼:我想知道,你在采访中的回答是什么.