使用尾递归查找二叉树的最大深度

Question

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

这个问题是在Leetcode教程中关于尾递归的练习题。 尾递归 - 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 

然而，这不是尾递归。

尾递归是一种递归形式，其中递归调用是递归函数的最后一个指令。而且在函数中应该只有一个递归调用。

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

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

- Alice

Answer 1

任何递归程序都可以被设计成栈安全的。

我已经写了很多关于递归的主题，当人们错误陈述事实时，我感到难过。而且，这不依赖于愚蠢的技巧，如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)
      )

这实际上是完全相同的程序。那么，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 表达式。这里的答案是我在这个问题和回答（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

栈 vs 堆

你不再受到Python约为1000的堆栈限制。我们有效地劫持了Python的求值策略，并编写了我们自己的替代品loop。我们不再将函数调用帧放置在栈上，而是将它们交换为“continuations”（延续）在堆上。现在唯一的限制是计算机的内存。

- Mulan

---

即使过了多年，我仍然觉得好像必须回到那个问答环节。很高兴看到你还在这里。 - Matus Dubrava

Answer 2

每个递归算法都可以转换为尾递归算法。有时候这并不直接，需要使用稍微不同的方法。

对于确定二叉树深度的尾递归算法，您可以通过累加子树列表以及深度信息来遍历树。因此，您的列表将是一个元组列表(depth: Int, node: tree)，第二个累加器将记录最大深度。

以下是算法的一般概述：

• 从包含元组(1, rootNode)的列表toVisit开始，并将maxDepth设置为0

1. 如果toVisit列表为空，则返回maxValue
2. 从列表中弹出头部
3. 如果头部是EmptyTree，则继续处理尾部，maxValue保持不变
4. 如果头部是Node，则通过将左右子树添加到其尾部、在元组中增加深度并检查弹出的头部的深度是否大于存储在maxDepth累加器中的深度来更新toVisit

以下是Scala实现：

abstract class Tree[+A] {
  def head: A
  def left: Tree[A]
  def right: Tree[A]
  def depth: Int
  ...
}
case object EmptyTree extends Tree[Nothing] {...}

case class Node[+A](h: A, l: Tree[A], r: Tree[A]) extends Tree[A] {

  override def depth: Int = {

    @tailrec
    def depthAux(toVisit: List[(Int, Tree[A])], maxDepth: Int): Int = toVisit match {
      case Nil => maxDepth
      case head :: tail => {
        val depth = head._1
        val node = head._2
        if (node.isEmpty) depthAux(tail, maxDepth)
        else depthAux(toVisit = tail ++ List((depth + 1, node.left), (depth + 1, node.right)),
                      maxDepth = if (depth > maxDepth) depth else maxDepth)
      }
    }

    depthAux(List((1, this)), 0)
  }
 ...
}

对于那些更感兴趣的 Haskell 的人

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

depthAux :: [(Int, Tree a)] -> Int -> Int
depthAux [] maxDepth = maxDepth
depthAux ((depth, Empty):xs) maxDepth = depthAux xs maxDepth
depthAux ((depth, (Node h l r)):xs) maxDepth = 
    depthAux (xs ++ [(depth + 1, l), (depth + 1, r)]) (max depth maxDepth) 

depth :: Tree a -> Int
depth node = depthAux [(1, node)] 0

- Matus Dubrava

Answer 3

你做不到。显然，要同时消除左侧尾调用和右侧尾调用是不可能的。你可以消除其中一个，但不能同时消除两个。让我们来谈谈这个问题。

---

让我们开门见山地说，递归通常在Python中是一个糟糕的主意。它不是为递归解决方案进行优化的，即使是微不足道的优化（如尾调用消除）也没有实现。这里不要这样做。

但是，它可以是一个很好的语言，用于说明在其他语言中可能更难理解的概念（即使这些可能更适合您正在寻找的解决方案类型），因此让我们深入探讨一下。

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

1. 基本情况

这是通常是像return 1或其他退化案例的琐碎案例。

2. 递归情况

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

对于尾递归而言，重要的部分在于递归情况中，函数不必在递归后执行任何操作。更优化的语言可以推导出这一点，并且在递归进入新调用时立即丢弃包含旧调用上下文的堆栈帧。通常通过函数参数传递所需的上下文来完成这一点。

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

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)

你看到我不得不定义一个帮助函数，它需要一些用户没有自然传递的参数吗？这可以帮助你解决这个问题。

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

- Adam Smith

---

我的原始代码在 go 中有一个错别字，它将 root.left 和 root.right 传递给了递归，而不是 node.left 和 node.right，因此它一直在递归。糟糕！ - Adam Smith

Answer 4

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

下面是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

- Pandermatt