blocks|key|5508895|text|一个简单的递归解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5508896|int+count()+{
+++Tree+l+=+getLeftTree();
+++Tree+r+=+getRightTree();
+++return+1+%2B+(l+!=+null+?+l.count()+:+0)+%2B+(r+!=+null+?+r.count()+:+0);
}|code-block|syntax|javascript|5508897|一个不那么微不足道的非递归函数：|5508898|int+count()+{
++++Stack<Tree>+s+=+new+Stack<Tree>();
++++s.push(this);
++++int+cnt+=+0;
++++while+(!s.empty())+{
++++++++Tree+t+=+s.pop();
++++++++cnt%2B%2B;
++++++++Tree+ch+=+getLeftTree();
++++++++if+(ch+!=+null)+s.push(ch);+
++++++++ch+=+getRightTree();
++++++++if+(ch+!=+null)+s.push(ch);+
++++}
++++return+cnt;
}|5508899|后者可能稍微更有效地利用内存，因为它用堆栈和迭代代替了递归。它也可能更快，但没有测量就很难判断。一个关键区别是递归解决方案使用堆栈，而非递归解决方案使用堆来存储节点。|5508900|编辑：这里是迭代解决方案的一个变体，它使用堆栈的次数较少：|offset|length|style|BOLD|5508901|int+count()+{
++++Tree+t+=+this;
++++Stack<Tree>+s+=+new+Stack<Tree>();
++++int+cnt+=+0;
++++do+{
++++++++cnt%2B%2B;
++++++++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;
}|5508902|您是否需要更有效的解决方案或更优雅的解决方案，自然取决于您的树的大小和您打算使用此例程的频率。记住Hoare说过的话：“过早优化是万恶之源。”|5508903|entityMap^0|0|0|0|0|0|0|3|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|10|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|12|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|13|8|@$O|14|P|15|Q|R]]|9|@]|A|$]]|$1|S|3|T|5|D|7|16|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|17|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|X|$]]

A trivial recursive solution:

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

A less trivial non-recursive one:

<pre><code>int count() {
 Stack&lt;Tree&gt; s = new Stack&lt;Tree&gt;();
 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;
}
</code></pre>

The latter is probably slightly more memory-efficient, because it replaces recursion with a stack and an iteration. It's also probably faster, but its hard to tell without measurements. A key difference is that the recursive solution uses the stack, while the non-recursive solution uses the heap to store the nodes.

Edit: Here's a variant of the iterative solution, which uses the stack less heavily:

<pre><code>int count() {
 Tree t = this;
 Stack&lt;Tree&gt; s = new Stack&lt;Tree&gt;();
 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;
}
</code></pre>

Whether you need a more efficient or a more elegant solution naturally depends on the size of your trees and on how often you intend to use this routine. Rembemer what Hoare said: "premature optimization is the root of all evil."

blocks|key|1980747|text|像这样的东西应该是有效的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1980748|int+count()
{
++++int+left+=+getLeftChild()+==+null+?+0+:+getLeftChild().count();
++++int+right+=+getRightChild()+==+null+?+0+:+getRightCHild().count();

++++return+left+%2B+right+%2B+1;
}|code-block|syntax|javascript|1980749|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Something like this should work:

<pre><code>int count()
{
 int left = getLeftChild() == null ? 0 : getLeftChild().count();
 int right = getRightChild() == null ? 0 : getRightCHild().count();

 return left + right + 1;
}
</code></pre>

blocks|key|4091371|text|这是一个标准的递归问题：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4091372|count():
++++cnt+=+1+//+this+node
++++if+(haveRight)+cnt+%2B=+right.count
++++if+(haveLeft)++cnt+%2B=+left.count
return+cnt;|code-block|syntax|javascript|4091373|效率非常低，如果树很深，这是一个杀手，但这对你来说是递归...|4091374|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

This is a standard recursion problem:

<pre><code>count():
 cnt = 1 // this node
 if (haveRight) cnt += right.count
 if (haveLeft) cnt += left.count
return cnt;
</code></pre>

Very inefficient, and a killer if the tree is very deep, but that's recursion for ya...

blocks|key|1980763|text|int+count()+{
++Tree+right+=+getRightChild();
++Tree+left+=+getLeftChild();
++int+c+=+1;++++++++++++++++++++++++++++++++++++++//+count+yourself!
++if+(+right+!=+null+)+c+%2B=+right.count();++++++++//+count+sub+trees
++if+(+left+!=+null+)+c+%2B=+left.count();++++++++++//+..
++return+c;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1980764|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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;
}
</code></pre>

blocks|key|5508940|text|return+(getRightChild()+==+null+?+0+:+getRightChild.count())+%2B+(getLeftChild()+==+null+?+0+:+getLeftChild.count())+%2B+1;|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|5508941|或者类似的东西。|unstyled|5508942|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;
</code></pre>

Or something like that.

blocks|key|1980801|text|你可以通过遍历许多ways来计算树的个数。简单的预排序遍历，代码将是(基于您定义的函数)：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1980802|int+count()+{
++++count+=+1;
++++if+(this.getLeftChild()+!=+null)
++++++++count+%2B=+this.getLeftChild().count();
++++if+(this.getRightChild()+!=+null)
++++++++count+%2B=+this.getRightChild().count();
++++return+count;
}|code-block|syntax|javascript|1980803|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Tree_traversal^0|9|4|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

You can count the tree by traversing it many <a href="http://en.wikipedia.org/wiki/Tree_traversal" rel="nofollow noreferrer">ways</a>. Simply preorder traversal, the code would be (based on the functions you defined):

<pre><code>int count() {
 count = 1;
 if (this.getLeftChild() != null)
 count += this.getLeftChild().count();
 if (this.getRightChild() != null)
 count += this.getRightChild().count();
 return count;
}
</code></pre>

blocks|key|4091436|text|int+count()

{
+++int+retval+=+1;
++++if(null+!=+getRightChild())+retval%2B=getRightChild().count();
++++if(null+!=+getLeftChild())+retval%2B=getLeftChild().count();
++++return+retval;

}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4091437|天哪，我希望我没弄错。|unstyled|4091438|编辑:实际上我是这样做的。|4091439|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|L|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|F|7|N|8|@]|9|@]|A|$]]]|J|$]]

<pre><code>int count()

{
 int retval = 1;
 if(null != getRightChild()) retval+=getRightChild().count();
 if(null != getLeftChild()) retval+=getLeftChild().count();
 return retval;

}
</code></pre>

God I hope I didn't make a mistake.

EDIT: I did actually.

blocks|key|1980846|text|我更喜欢这个，因为它是这样写的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1980847|返回左侧计数%2B右侧计数%2B1|1980848|++int+count()+{
++++++return++countFor(+getLeftChild()+)+%2B+countFor(+getRightChild()+)+%2B+1;
++}
++private+int+countFor(+Tree+tree+)++{+
+++++++return+tree+==+null+?+0+:+tree.count();
++}|code-block|syntax|javascript|1980849|更倾向于识字编程。|1980850|顺便说一句，我不喜欢在Java上常用的getter/setter约定，我认为使用leftChild()会更好：|1980851|++return+countFor(+leftChild()+)+%2B+countFor(+rightChild()+)+%2B+1;|1980852|就像Hoshua+Bloch在min的http://www.youtube.com/watch?v=aAb7hSCtvGw解释的那样。32:03|offset|length|1980853|1980854|如果你让它正确，你的代码读起来...|blockquote|1980855|1980856|1980857|但是，我必须承认get/set约定现在几乎是语言的一部分。:)|1980858|对于许多其他部分，遵循此策略可以创建自文档化代码，这是一件好事。|1980859|托尼:我想知道，你在面试中的回答是什么？|1980860|entityMap|0|LINK|mutability|MUTABLE|url|http://www.youtube.com/watch?v=aAb7hSCtvGw^0|0|0|0|0|0|0|J|16|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1D|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1E|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|1F|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1G|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|1H|8|@]|9|@]|A|$G|H]]|$1|O|3|P|5|6|7|1I|8|@]|9|@$Q|1J|R|1K|1|1L]]|A|$]]|$1|S|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]|$1|T|3|U|5|V|7|1N|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|1O|8|@]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1P|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|1R|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1S|8|@]|9|@]|A|$]]|$1|14|3|-4|5|6|7|1T|8|@]|9|@]|A|$]]]|15|$16|$5|17|18|19|A|$1A|1B]]]]

I like this better because it reads:

return count for left + count for rigth + 1 

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

A little more towards literate programming.

BTW, I don't like the getter/setter convention that is so commonly used on Java, I think a using leftChild() instead would be better:

<pre><code> return countFor( leftChild() ) + countFor( rightChild() ) + 1;
</code></pre>

Just like Hoshua Bloch explains here <a href="http://www.youtube.com/watch?v=aAb7hSCtvGw" rel="noreferrer">http://www.youtube.com/watch?v=aAb7hSCtvGw</a> at min. 32:03

<blockquote>
 If you get it rigth your code reads...
</blockquote>

BUT, I have to admit the get/set convention is now almost part of the language. :) 

For many other parts, following this strategy creates self documenting code, which is something good.

Tony: I wonder, what was your answer in the interview.

blocks|key|1607465|text|当然，如果您想要避免在计数时访问树中的每个节点，并且处理时间对您来说比内存更有价值，那么您可以在构建树时通过创建计数来欺骗。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1607466|1607467|在每个节点中都有一个整数计数，该计数初始化为1，它表示以该节点为根的子树中的节点数。|ordered-list-item|1607468|当您插入节点时，在从递归插入例程返回之前，在当前节点上递增计数。|1607469|1607470|即|1607471|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%2B%2B;
}|code-block|syntax|javascript|1607472|然后，从任意点获取计数只需要查找node.count|1607473|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|V|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|W|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|Y|8|@]|9|@]|A|$]]|$1|K|3|L|5|M|7|Z|8|@]|9|@]|A|$N|O]]|$1|P|3|Q|5|6|7|10|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|S|$]]

Of course, if you want to avoid visiting every node in your tree when you count, and processing time is worth more to you than memory, you can cheat by creating your counts as you build your tree.

<ol>
<li>Have an int count in each node,
initialized to one, which
respresents the number of nodes in
the subtree rooted in that node.</li>
<li>When you insert a node, before
returning from your recursive insert
routine, increment the count at the
current node.</li>
</ol>

i.e. 

<pre><code>public void insert(Node root, Node newNode) {
 if (newNode.compareTo(root) &gt; 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++;
}
</code></pre>

Then getting the count from any point just involves a lookup of node.count

blocks|key|1611047|text|class+Tree+{

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

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

++int+count()+{
+++return+1+
++++++%2B+getRightChild()+==+null?+0+:+getRightChild().count()
++++++%2B+getLeftChild()+==+null?+0+:+getLeftChild().count();
++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1611048|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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();
 }
}
</code></pre>

blocks|key|4091516|text|我的第一次尝试没有添加任何新的东西，但是后来我开始想知道递归深度，以及是否可以重新排列代码以利用最新Java编译器的尾部调用优化特性。主要的问题是空测试--这可以使用NullObject来解决。我不确定TCO是否可以处理这两个递归调用，但它至少应该优化最后一个。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4091517|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+%2B+right.count()+%2B+left.count();
}+++|code-block|syntax|javascript|4091518|NullNode的精确实现依赖于树中使用的实现-如果树使用NullNode而不是null，那么也许子访问方法应该抛出NullPointerException而不是返回null。无论如何，主要的想法是使用NullObject，以便尝试从总体拥有成本中获益。|4091519|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

My first attempt didn't have anything new to add, but then I started to wonder about recursion depth and whether it would be possible to rearrange the code to take advantage of the tail call optimization feature of the latest Java compiler. The main problem was the null test - which can be solved using a NullObject. I'm not sure if TCO can deal with both recursive calls, but it should at least optimize the last one.

<pre><code>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();
} 
</code></pre>

The precise implementation of NullNode depends on the implementations used in Tree - if Tree uses NullNode instead of null, then perhaps the child access methods should throw NullPointerException instead of returning null. Anyway, the main idea is to use a NullObject in order to try to benifit from TCO.

blocks|key|5509086|text|实现该方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5509087|public+static+int+countOneChild(Node+root)
{
++++...
}|code-block|syntax|javascript|5509088|它计算具有一个子节点的二叉树中的内部节点的数量。将函数添加到tree.java程序中。|offset|length|style|CODE|5509089|entityMap^0|0|0|U|9|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Implement the method:

<pre><code>public static int countOneChild(Node root)
{
 ...
}
</code></pre>

that counts the number of internal nodes in a binary tree having one child. Add the function to <code>tree.java</code> program.

blocks|key|4091562|text|与二叉树相关的问题应该会在面试中出现。我想说的是，在任何下一次面试之前，要花点时间通过this链接。.You可以查看大约14个已解决的问题，以及解决方案是如何完成的。这将使您了解如何在将来使用二叉树解决问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4091563|我知道您的问题是关于count方法的，.That也在我提供的链接中实现|4091564|entityMap|0|LINK|mutability|MUTABLE|url|http://cslibrary.stanford.edu/110/BinaryTrees.html^0|17|4|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Questions related to binary tree should be expected in an interview. I would say to take time before any next interview and go through <a href="http://cslibrary.stanford.edu/110/BinaryTrees.html" rel="nofollow">this</a> link. There are about 14 problems solved .You can have a look and how the solution is done. This would give you an idea of how to tackle a problem with binary tree in future.

I know your question is specific to the count method .That is also implemented in the link that i provided

blocks|key|4091568|text|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+%2B+this.getLeftChild().count()+%2B+this.getRightChild().count();
++++elseif(this.getLeftChild()+!=null+&&+this.getRightChild()==null)
++++++++return+1+%2B+this.getLeftChild().count();
++++elseif(this.getLeftChild()+==null+&&+this.getRightChild()!=null)
++++++++return+1+%2B+this.getRightChild().count();
++++else+return+1;//left+&+right+sub+trees+are+null+==>+count+the+root+node
++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4091569|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>class Tree {

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

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

 int count() {
 if(this.getLeftChild() !=null &amp;&amp; this.getRightChild()!=null) 
 return 1 + this.getLeftChild().count() + this.getRightChild().count();
 elseif(this.getLeftChild() !=null &amp;&amp; this.getRightChild()==null)
 return 1 + this.getLeftChild().count();
 elseif(this.getLeftChild() ==null &amp;&amp; this.getRightChild()!=null)
 return 1 + this.getRightChild().count();
 else return 1;//left &amp; right sub trees are null ==&gt; count the root node
 }
}
</code></pre>

blocks|key|1981011|text|我是通过预序递归来实现的。虽然它并不完全遵循localRoot的面试格式，但我想你已经明白了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1981012|private+int+countNodes(Node<E>+localRoot,+int+count)+{
++++if+(localRoot+==+null)+
++++++++return+count;+++++
++++count%2B%2B;+//+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);
}|code-block|syntax|javascript|1981013|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I did it by preorder recurssion. Altough it doesn't exactly follow the interview format by using localRoot, but I think you get the idea.

<pre><code>private int countNodes(Node&lt;E&gt; 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);
}
</code></pre>

First of all, I swear this is not homework, it's a question I was asked in an interview. I think I made a mess of it (though I did realise the solution requires recursion). Here is the question:

Implement the count() method which returns the number of nodes in a tree. If a node doesn't have either a left or right child, the relevant <code>getXXChild()</code> method will return <code>null</code>

<pre><code>class Tree {

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

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

 int count() {
 // Implement me
 }
}
</code></pre>

My reason for asking the question is simply curious to see the correct solution, and thereby measure how bad mine was.

Cheers,
Tony

Counting nodes in a tree in Java

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

首先，我发誓这不是家庭作业，这是我在面试中被问到的一个问题。我想我把它搞得一团糟(尽管我确实意识到解决方案需要递归)。下面是问题：实现count()方法，该方法返回树中的节点数。如果节点既没有左子节点也没有右子节点，则相关的getXXChild()方法将返回nullclass Tree {  Tree getRight...

问在Java中计算树中的节点
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Java中计算树中的节点EN