python - 使用尾递归找到二叉树的最大深度

Question

我正在努力解决一个问题Maximum Depth of Binary Tree - LeetCode

该问题在 leetcode 教程中作为尾递归练习给出。 tail recursion - LeetCode

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

从层次定义看问题的标准解

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """ 
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1 

但是，它不是尾递归

Tail recursion is a recursion where the recursive call is the final instruction in the recursion function. And there should be only one recursive call in the function.

我阅读了所有其他提交和讨论，但没有找到尾递归解决方案。

如何使用尾递归解决问题？

Answer 1

任何递归程序都可以是栈安全的

我已经写了很多关于递归的文章，当人们错误地陈述事实时我很难过。不，这确实不依赖于 sys.setrecursionlimit() 等愚蠢的技术。

在 python 中调用一个函数会添加一个栈帧。因此，我们不会编写 f(x) 来调用函数，而是编写 call(f,x)。现在我们可以完全控制评估策略 -

# btree.py

def depth(t):
  if not t:
    return 0
  else:
    return call \
      ( lambda left_height, right_height: 1 + max(left_height, right_height)
      , call(depth, t.left)
      , call(depth, t.right)
      )

实际上是完全相同的程序。那么什么是call呢？

# tailrec.py

class call:
  def __init__(self, f, *v):
    self.f = f
    self.v = v

所以 call 是一个具有两个属性的简单对象:要调用的函数 f 和调用它的值 v .这意味着 depth 返回一个 call 对象而不是我们需要的数字。只需要再调整一次 -

# btree.py

from tailrec import loop, call

def depth(t):
  def aux(t):                        # <- auxiliary wrapper
    if not t:
      return 0
    else:
      return call \
        ( lambda l, r: 1 + max(l, r)
        , call(aux, t.left)
        , call(aux, t.right)
        )
  return loop(aux(t))                # <- call loop on result of aux

循环

现在我们需要做的就是编写足够熟练的 loop 来评估我们的 call 表达式。这里的答案是我在this Q&A写的评估器的直接翻译(JavaScript)。我不会在这里重复自己的话，所以如果您想了解它是如何工作的，我会在该帖子中构建 loop 时逐步解释它 -

# tailrec.py

from functools import reduce

def loop(t, k = identity):
  def one(t, k):
    if isinstance(t, call):
      return call(many, t.v, lambda r: call(one, t.f(*r), k))
    else:
      return call(k, t)
  def many(ts, k):
    return call \
      ( reduce \
          ( lambda mr, e:
              lambda k: call(mr, lambda r: call(one, e, lambda v: call(k, [*r, v])))
          , ts
          , lambda k: call(k, [])
          )
      , k
      )
  return run(one(t, k))

注意到一种模式了吗？ loop 的递归方式与 depth 相同，但我们在这里也使用 call 表达式进行递归。请注意 loop 如何将其输出发送到 run，其中会发生明确无误的迭代 -

# tailrec.py

def run(t):
  while isinstance(t, call):
    t = t.f(*t.v)
  return t

检查你的工作

from btree import node, depth

#   3
#  / \
# 9  20
#   /  \
#  15   7

t = node(3, node(9), node(20, node(15), node(7)))

print(depth(t))

3

堆栈与堆

您不再受限于 python 的 ~1000 堆栈限制。我们有效地劫持了 python 的评估策略并编写了我们自己的替代品，loop。我们不是将函数调用帧扔到堆栈上，而是将它们换成堆上的延续。现在唯一的限制是您计算机的内存。