首先，我发誓这不是作业，这是我在一次采访中被问到的一个问题。我想我把它弄得一团糟（尽管我确实意识到解决方案需要递归）。这是问题：
实现 count() 方法，该方法返回树中的节点数。如果一个节点既没有左孩子也没有右孩子，相关的getXXChild()方法将返回null
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
// Implement me
}
}
我问这个问题的原因只是想看看正确的解决方案，从而衡量我的问题有多糟糕。
干杯，托尼
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;
}
一个简单的递归解决方案：
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;
}
您是否需要更高效或更优雅的解决方案自然取决于您的树的大小以及您打算使用此例程的频率。记住 Hoare 所说的：“过早的优化是万恶之源。”
我更喜欢这个，因为它写着：
左返回计数 + 右计数 + 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 at min。32:03
如果你得到它rigth你的代码读取......
但是，我不得不承认 get/set 约定现在几乎是语言的一部分。:)
对于许多其他部分，遵循此策略会创建自记录代码，这是一件好事。
托尼：我想知道，你在采访中的回答是什么。
像这样的东西应该工作：
int count()
{
int left = getLeftChild() == null ? 0 : getLeftChild().count();
int right = getRightChild() == null ? 0 : getRightCHild().count();
return left + right + 1;
}
return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;
或类似的东西。
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
return 1
+ getRightChild() == null? 0 : getRightChild().count()
+ getLeftChild() == null? 0 : getLeftChild().count();
}
}
您可以通过多种方式遍历这棵树。简单地预先遍历，代码将是（基于您定义的函数）：
int count() {
count = 1;
if (this.getLeftChild() != null)
count += this.getLeftChild().count();
if (this.getRightChild() != null)
count += this.getRightChild().count();
return count;
}
实现方法：
public static int countOneChild(Node root)
{
...
}
它计算具有一个孩子的二叉树中的内部节点的数量。将功能添加到tree.java程序中。
我是通过前序递归做到的。虽然它并不完全遵循使用 localRoot 的采访格式，但我想你明白了。
private int countNodes(Node<E> localRoot, int count) {
if (localRoot == null)
return count;
count++; // Visit root
count = countNodes(localRoot.left, count); // Preorder-traverse (left)
count = countNodes(localRoot.right, count); // Preorder-traverse (right)
return count;
}
public int countNodes() {
return countNodes(root, 0);
}
这是一个标准的递归问题：
count():
cnt = 1 // this node
if (haveRight) cnt += right.count
if (haveLeft) cnt += left.count
return cnt;
非常低效，如果树很深，这是一个杀手，但这对你来说是递归......
int count()
{
int retval = 1;
if(null != getRightChild()) retval+=getRightChild().count();
if(null != getLeftChild()) retval+=getLeftChild().count();
return retval;
}
上帝，我希望我没有犯错。
编辑：我确实做到了。
我的第一次尝试没有添加任何新内容，但后来我开始怀疑递归深度以及是否可以重新排列代码以利用最新 Java 编译器的尾调用优化功能。主要问题是空测试 - 可以使用 NullObject 解决。我不确定 TCO 是否可以处理这两个递归调用，但它至少应该优化最后一个。
static class NullNode extends Tree {
private static final Tree s_instance = new NullNode();
static Tree instance() {
return s_instance;
}
@Override
Tree getRightChild() {
return null;
}
@Override
Tree getLeftChild() {
return null;
}
int count() {
return 0;
}
}
int count() {
Tree right = getRightChild();
Tree left = getLeftChild();
if ( right == null ) { right = NullNode.instance(); }
if ( left == null ) { left = NullNode.instance(); }
return 1 + right.count() + left.count();
}
NullNode 的精确实现取决于 Tree 中使用的实现——如果 Tree 使用 NullNode 而不是 null，那么子访问方法可能应该抛出 NullPointerException 而不是返回 null。无论如何，主要思想是使用 NullObject 以尝试从 TCO 中受益。
当然，如果您想在计数时避免访问树中的每个节点，并且处理时间对您来说比内存更有价值，您可以通过在构建树时创建计数来作弊。
在每个节点中都有一个 int 计数，初始化为 1，它表示以该节点为根的子树中的节点数。
插入节点时，在从递归插入例程返回之前，增加当前节点的计数。
IE
public void insert(Node root, Node newNode) {
if (newNode.compareTo(root) > 1) {
if (root.right != null)
insert(root.right, newNode);
else
root.right = newNode;
} else {
if (root.left != null)
insert(root.left, newNode);
else
root.left = newNode;
}
root.count++;
}
然后从任何点获取计数只涉及查找 node.count
在面试中应该预料到与二叉树有关的问题。我会说在下一次面试之前花点时间浏览这个链接。解决了大约14个问题。您可以看看解决方案是如何完成的。这将使您了解将来如何解决二叉树的问题。
我知道您的问题特定于 count 方法。这也在我提供的链接中实现
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
if(this.getLeftChild() !=null && this.getRightChild()!=null)
return 1 + this.getLeftChild().count() + this.getRightChild().count();
elseif(this.getLeftChild() !=null && this.getRightChild()==null)
return 1 + this.getLeftChild().count();
elseif(this.getLeftChild() ==null && this.getRightChild()!=null)
return 1 + this.getRightChild().count();
else return 1;//left & right sub trees are null ==> count the root node
}
}