擅长:python、mysql、java
<p>递归地计算两个子节点非常简单。如果每次函数调用都返回一个数字(基本情况为零),则每次找到两个子节点时,只需添加1即可:</p>
<pre><code>def findDoubleNodes(tree):
if tree == None or (tree.left == None and tree.right == None):
# base case
return 0
elif tree.left <> None and tree.right <> None:
# both have children, so add one to our total and go down one level
return findDoubleNodes(tree.left)+findDoubleNodes(tree.right) + 1
else:
# only one child, so only go down one level
return findDoubleNodes(tree.left)+findDoubleNodes(tree.right)
</code></pre>
<p>输入<code>RefBinaryTree</code>返回有两个子节点的节点数。例如:</p>
^{pr2}$
<p>(懒洋洋地)创建的树如下所示:</p>
<pre><code> 1
/
5
/ \
6 7
/ \
8 9
\
10
</code></pre>
<p>而<code>findDoubleNodes(x)</code>返回{<cd3>},因为只有两个节点(5和7)有两个子节点。在</p>
<p>另外,向节点9(<code>x.left.right.right.insert_left(11)</code>)添加一个左子节点可以得到预期的结果,返回<code>3</code>。在</p>