擅长:python、mysql、java
<p>对于这个特殊的问题,您需要遍历整个树并返回看到的最小值。但是一般来说,递归的基本原理是,当你再次调用这个函数时,你会遇到同样问题的一个修改版本。</p>
<p>想想你的树:</p>
<pre><code> root
/ \
left right
</code></pre>
<p>当您调用左子树上的递归函数时,您将再次看到一棵树。因此,您应该能够使用相同的逻辑。</p>
<p>递归函数的关键是基本情况和递归步骤。在您的树示例中,基本情况不是在找到最小值时(您如何知道?)而是当你到达树的底部(又称叶子)。</p>
<p>而且,递归步骤是查看每个子问题(bin_min(左)和bin_min(右))。</p>
<p>最后一件是考虑返回值。不变量是您的函数返回了它所看到的最小元素。因此,当递归调用返回时,您知道它是最小的元素,然后您需要返回的是三个可能选择(根、左、右)中最小的元素。</p>
<pre><code>def min_bin(root):
if not root:
return MAX_VAL
left_min = min_bin(root.left)
right_min = min_bin(root.right)
return min(left_min, right_min, root.val)
</code></pre>
<p>注意,这是一个不同于@Rik Poggi的解决方案。他使用尾部递归来优化它。</p>