104. Maximum Depth of Binary Tree (Easy)

更新于 阅读次数： 本文字数： 714 阅读时长 ≈ 1 分钟

求二叉树的最大深度。二叉树的深度指的是其节点的最大层数。

这是一道简单题，但是可以视作是 Top-Down 和 Bottom-Up 方法的教学题。

我们应用 DFS 来处理之道题，来看看自上而下与自下而上方法的区别。

思路 1，Top-Down，递归

在递归过程中，我们先根据当前层的深度更新结果，然后针对子节点进行递归调用，重复这个过程直到遍历完整棵树。这是从上至下的解题方法，顺序体现在我们何时处理当前节点的值。

这个思路可以解决问题，但是从逻辑上来说，如果存在子节点，那么当前节点的深度肯定不是最终答案，Top-Down 方法或许不是最符合这道题目逻辑的方法。

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        ans = 0

        def traverse(node, depth):
            if not node:
                return
            nonlocal ans
            ans = max(ans, depth)
            traverse(node.left, depth + 1)
            traverse(node.right, depth + 1)

        traverse(root, 1)
        return ans

思路 2，Bottom-Up，递归

在从下至上的方法中，我们先去计算以当前节点开始其子节点的最大深度，在结果的基础上 +1 作为当前节点的深度结束递归过程。

class Solution:
    def maxDepth(self, root: TreeNode) -> int:

        def traverse(node):
            if not node:
                return 0
            return 1 + max(traverse(node.left),
                           traverse(node.right))

        return traverse(root)
相关文章