【Leetcode Daily】104二叉树的最大深度

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是规定二叉树的深度是从根节点到叶子节点的节点数，求二叉树的最大深度。

思路分享

• 题不难，重点是开始尝试理解二叉树中 “自顶向下” 和 “自底向上” 的区别。

  https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/2010612/kan-wan-zhe-ge-shi-pin-rang-ni-dui-di-gu-44uz/

• 这个区别灵神没有明说，这里记录一下自己的见解：自底向上的值传递就和名字一样，就是从下向上通过返回值传，这里的下指的是递归终止的条件，从铺设递归的条件开始思考，逐步补全整体的递归；自顶向下则是将答案和中间值的记录，通过函数外的变量或是函数的参数传递，整体可能与自底向上差不多，只是会在中间引入外界变量记录答案，不会用返回值。

代码解答（强烈建议自行解答后再看）

• 参考题解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 自顶向下
        ans = 0
        def dfs(root: Optional[TreeNode], depth: int) -> int:
            if not root:
                return
            depth += 1
            nonlocal ans
            ans = max(ans, depth)
            dfs(root.left, depth)
            dfs(root.right, depth)
        dfs(root, 0)
        return ans


        # 自底向上
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1