<p>有两种方法可以做到这一点。</p>
<hr/>
<p>简单的方法是<code>return</code>每个递归调用的计数,而不仅仅是<code>print</code>并递增:</p>
<pre><code>def BST_size(root):
if root is None:
return -1
if root is not None:
if root.left is not None:
return 1 + BST_size(root.left)
if root.right is not None:
return 1 + BST_size(root.right)
def print_BST_size(root):
size = BST_size(root)
if size == -1:
print "size -1 (Null value in root)"
else:
print "size", size
</code></pre>
<p>但是,这仍然不起作用,因为您只遍历左侧<em>或</em>右侧,而不是同时遍历两者。你想要的是:</p>
<pre><code> count = -1
if root is not None:
if root.left is not None:
count += BST_size(root.left)
if root.right is not None:
count += BST_size(root.right)
return count
</code></pre>
<hr/>
<p>不过,看起来您正在尝试使用累加器,采用尾部递归样式。在Python中这样做是没有意义的,因为Python没有优化尾部调用,但是对于其他语言和理论上的原因来说,这是一项很有用的技能,所以</p>
<p>这里的问题是,您需要所有递归调用共享同一个值,这意味着您需要一个可变值。所以,你可以从<code>[0]</code>开始而不是<code>0</code>,从<code>count[0] += 1</code>开始而不是<code>count += 1</code>。</p>
<p>或者,您可以重新排列代码,使其不可变地使用<code>count</code>,而是将更新后的计数从一侧向下传递到另一侧。</p>
<hr/>
<p>不管怎样,你的代码还有一个问题。递归的基本情况是<code>root</code>是<code>None</code>。但你也把它做成了一个特例,打印-1而不是0。你不能两全其美。</p>