【Day 13】 二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:  叶子节点是指没有子节点的节点。

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

    3

/ \
 9 20
/ \
 15 7
返回它的最大深度  3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时间复杂度 O(n)

var maxDepth = function (root) {
    if (root == null) {
        return 0
    } else {
        let left = maxDepth(root.left)
        let right = maxDepth(root.right)
        console.log(left)
        return Math.max(left, right) + 1
    }
};

参考回答

前置知识

• 递归

思路

树的题目很适合用来递归来做。 基本上和树的搜索有关的，都可以用递归来做，为什么？

因为树是一种递归的数据结构。而穷举搜索一棵树必然需要遍历其所有节点，而搜索的逻辑对所有的子树都是一样的。因此这就很适合用递归来解决了。

这里给大家介绍一种写递归的小方法 产品经理法。

1. 定义函数功能，不用管其具体实现。

从高层次的角度来定义函数功能。 你可以把自己想象成产品经理。只需要知道要做什么事情就行了，而怎么实现我不管，那是码农的事情。

具体来说，我需要的功能是给定一个二叉树的节点，返回以这个节点为根节点的子树的最大深度。假设这个函数为 f。那么问题转化为 f(root)。

1. 确定大问题和小问题的关系。

要解决 f(root) 这个问题。可以先解决 f(root.right) 和 f(root.left)，当然我们仍然不关心 f 怎么实现。

f(root) 与 f(root.right) 和 f(root.left) 有什么关系呢？ 不难看出 1 + max(f(root.right), f(root.left))。

到这里我们还不知道 f 怎么实现的，但是我们已经完成了产品经理的需求。

实际上我们知道了，我们怎么知道的？

1. 补充递归终止条件。

如果递归到叶子节点的时候，返回 0 即可。

代码（Python）

# Definition for a binary tree node.
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为节点数。
• 空间复杂度：$O(h)$，其中 $h$ 为树的深度，最坏的情况 $h$ 等于 $N$，其中 N 为节点数，此时树退化到链表。