使用尾部递归查找二叉树的maxDepth

Question

我正在努力解决一个问题二叉树的最大深度-LeetCode

这个问题是在leetcode教程中作为尾递归练习给出的。尾递归-LeetCode

给定一棵二叉树，求其最大深度。

最大深度是从根节点到最远叶节点的最长路径上的节点数。

注意：叶子是没有子节点的节点。

例子：

给定二叉树[3,9,20，null，null，15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回其深度=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 

然而，它不是尾部递归

尾递归是递归，其中递归调用是递归函数中的最终指令。并且函数中应该只有一个递归调用。

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

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

Answer 1

这可能有点晚，但是您可以传递子树列表，并始终删除根元素。对于每个递归，您可以计算删除的数量。

Haskell中的一个实现

data Tree a 
    = Leaf a
    | Node a (Tree a) (Tree a)
    deriving Show

depth :: Tree a -> Integer
depth tree = recursion 0 [tree]
    where 
        recursion :: Integer -> [Tree a] -> Integer
        recursion n [] = n
        recursion n treeList = recursion (n+1) (concatMap f treeList)
            where
                f (Leaf _) = []
                f (Node _ left right) = [left, right]

root = Node 1 (Node 2 (Leaf 3) (Leaf 3)) (Leaf 7)

main :: IO ()
main = print $ depth root

Answer 2

你不能。你可以看到不可能同时消除所有的LHS尾部调用和RHS尾部调用。可以消除其中一个，但不能消除另一个。让我们谈谈这个。

首先，让我们直言不讳地说明递归在Python中通常是个坏主意。它没有针对递归解决方案进行优化，甚至没有实现琐碎的优化（如尾部调用消除）。别在这里这么做。

但是，它可以是一种很好的语言，用于说明在其他语言中可能难以掌握的概念（即使这些语言可能更适合您正在寻找的解决方案），所以让我们深入研究一下。

正如你所理解的：递归是一个调用自己的函数。虽然每个函数的逻辑可能会改变，但它们都有两个主要部分：

1. 基本情况

这是一个普通的情况，通常类似于return1或其他退化情况

这里是函数决定它必须深入并递归到自身的地方。

对于尾部递归，重要的部分是在递归情况下，函数在递归之后不必做任何事情。更优化的语言可以推断出这一点，并在旧调用递归到新调用时立即丢弃包含旧调用上下文的堆栈框架。这通常是通过将所需的上下文传递给函数参数来实现的。

想象一下这样实现的求和函数

def sum_iterative(some_iterable: List[int]) -> int:
    total = 0
    for num in some_iterable:
        total += num
    return total

def sum_recursive(some_iterable: List[int]) -> int:
    """This is a wrapper function that implements sum recursively."""

    def go(total: int, iterable: List[int]) -> int:
        """This actually does the recursion."""
        if not iterable:  # BASE CASE if the iterable is empty
            return 0
        else:             # RECURSIVE CASE
            head = iterable.pop(0)
            return go(total+head, iterable)

    return go(0, some_iterable)

你知道我是如何定义一个helper函数的吗？它接受一些用户不能自然传入的参数？这对你有帮助。

def max_depth(root: Optional[TreeNode]) -> int:
    def go(maxdepth: int, curdepth: int, node: Optional[TreeNode]) -> int:
        if node is None:
            return maxdepth
        else:
            curdepth += 1
            lhs_max = go(max(maxdepth, curdepth), curdepth, node.left)
            # the above is the call that cannot be eliminated
            return go(max(lhs_max, curdepth), curdepth, node.right)
    return go(0, 0, root)

有趣的是，这里有一个Haskell中非常丑陋的例子（因为我想重温一下我的功能性语言）

data TreeNode a = TreeNode { val   :: a
                           , left  :: Maybe (TreeNode a)
                           , right :: Maybe (TreeNode a)
                           }
treeDepth :: TreeNode a -> Int
treeDepth = go 0 0 . Just
  where go :: Int -> Int -> (Maybe (TreeNode a)) -> Int
        go maxDepth _        Nothing     = maxDepth
        go maxDepth curDepth (Just node) = let curDepth' = curDepth + 1 :: Int
                                               maxDepth' = max maxDepth curDepth' :: Int
                                               lhsMax    = go maxDepth' curDepth' (left node)
                                           in  go lhsMax curDepth' (right node)

root = TreeNode 3 (Just (TreeNode 9 Nothing Nothing)) (Just (TreeNode 20 (Just (TreeNode 15 Nothing Nothing)) (Just (TreeNode 7 Nothing Nothing)))) :: TreeNode Int

main :: IO ()
main = print $ treeDepth root

Answer 3

任何递归程序都可以使堆栈安全

我写了很多关于递归的文章，当人们误述事实时，我很难过。不，这并不依赖于像sys这样愚蠢的技术。setrecursionlimit（）。

在python中调用函数会添加堆栈帧。因此，我们将编写call（f，x）来调用函数，而不是编写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)
      )

它实际上是完全相同的程序。那么什么是呼叫？

# tailrec.py

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

所以call是一个简单的对象，有两个属性：要调用的函数，f，和调用它的值，v。这意味着深度正在返回一个调用对象，而不是我们需要的数字。只需要再做一次调整

# 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

环

现在我们所需要做的就是编写一个足够熟练的循环来计算我们的调用表达式。这里的答案是我在这个Q中写的评估者的直接翻译

# 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))

注意到一种模式吗<代码>循环与深度的递归方式相同，但我们也使用调用表达式在这里重复。请注意循环如何将其输出发送到运行，在那里会发生无误的迭代-

# 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的评估策略，并编写了我们自己的替换，循环。我们不把函数调用帧扔到堆栈上，而是用它们换取堆上的延续。现在唯一的限制是你电脑的内存。