二叉树的最大深度

2020-08-14 约 580 字预计阅读 2 分钟次阅读

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

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

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

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

最近做了一些题，看到总有人利用递归的思想解决问题，深深地被套娃😂吸引，拒绝套娃真香……

树本身就是套娃，天生适合递归的结构。

这里给出别人的优秀总结!!!：递归三部曲

找终止条件。 什么情况下递归结束？（一般n为0或者1），这里当然是树为空的时候，此时树的深度为0，递归就结束了。
找返回值。 应该返回什么？（一般为所求目标的同类型值）题目求的是树的最大深度，需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此返回值应该是当前树的最大深度，这一步可以结合第三步来看。
本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是最简单的样子。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度x和y。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度max(x,y)+1，然后再返回这个深度即可。

1
2
3


      root(max(x,y)+1)
      / \
 (x)left right(y)

代码如下：

1
2
3
4
5
6
7


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_deepth = self.maxDepth(root.left)
        right_deepth = self.maxDepth(root.right)
        return max(left_deepth, right_deepth) + 1