<p>这个答案假设您希望对发生在<code>left</code>分支中的每个<code>val</code>求和。我们希望求和的数字如下所示<code>(n)</code>-</p>
<pre class="lang-py prettyprint-override"><code># 6
# / \
# (5) 8
# / / \
# (3) (4) 9
# / \ /
# (1) 7 (2)
</code></pre>
<p>使用<code>TreeNode</code>类,我们构建<code>my_tree</code>-</p>
<pre class="lang-py prettyprint-override"><code>my_tree = \
TreeNode \
( 6
, TreeNode
( 5
, TreeNode(3, TreeNode(1), TreeNode(7))
, None
)
, TreeNode
( 8
, TreeNode(4)
, TreeNode(9, TreeNode(2), None)
)
)
</code></pre>
<p>递归是一种函数遗产,因此将其与函数风格结合使用会产生最好的结果。这意味着避免突变、变量重新分配和其他副作用。我们可以将<code>sum_left</code>作为一个普通函数写入<code>TreeNode</code>-</p>
<pre class="lang-py prettyprint-override"><code>def sum_left (t, is_left=False):
if not t:
return 0
else:
return \
(t.val if is_left else 0) \
+ sum_left(t.left, True) \
+ sum_left(t.right, False)
</code></pre>
<p>这是下面说同样事情的不那么冗长的方式-</p>
<pre class="lang-py prettyprint-override"><code>def sum_left (t, is_left=False):
if not t:
return 0
elif is_left:
return t.val + sum_left(t.left, True) + sum_left(t.right, False)
else:
return 0 + sum_left(t.left, True) + sum_left(t.right, False)
</code></pre>
<p>现在让我们看看计算的<code>sum_left</code></p>
<pre class="lang-py prettyprint-override"><code>print(sum_left(my_tree))
# 5 + 3 + 1 + 4 + 2
</code></pre>
<pre class="lang-py prettyprint-override"><code>=> 15
</code></pre>
<hr/>
<p>另一种选择是使用<a href="https://en.wikipedia.org/wiki/Mutual_recursion" rel="nofollow noreferrer">mutual recursion</a>-</p>
<pre class="lang-py prettyprint-override"><code>def sum_left (t):
if not t:
return 0
else:
return t.val + sum_left(t.left) + sum_right(t.right)
def sum_right (t):
if not t:
return 0
else:
return sum_left(t.left) + sum_right(t.right)
</code></pre>
<p>在这里,处理根节点的方式会有所不同。直接在根上调用<code>sum_left</code>也将对根节点求和-</p>
<pre><code>print(sum_left(my_tree))
# 6 + 5 + 3 + 1 + 4 + 2
</code></pre>
<pre class="lang-py prettyprint-override"><code>=> 21
</code></pre>
<p>如果要排除根节点,可以调用左节点上的<code>sum_left</code>和右分支上的<code>sum_right</code></p>
<pre class="lang-py prettyprint-override"><code>print(sum_left(my_tree.left) + sum_right(my_tree.right))
# 5 + 3 + 1 + 4 + 2
</code></pre>
<pre class="lang-py prettyprint-override"><code>=> 15
</code></pre>
<p>或者,看似违反直觉,只需在<code>my_tree</code>上调用<code>sum_right</code></p>
<pre class="lang-py prettyprint-override"><code>print(sum_right(my_tree))
# 5 + 3 + 1 + 4 + 2
</code></pre>
<pre class="lang-py prettyprint-override"><code>=> 15
</code></pre>