LeetCode | 二叉树的最大深度

分类：二叉树 / 深度优先搜索 / 递归

题目#

给定一棵二叉树的根节点 root，返回这棵树的最大深度。

最大深度指的是：从根节点到最远叶子节点经过的节点个数。

示例：

1
        3
2
       / \
3
      9   20
4
         /  \
5
        15   7
6

7
输入：root = [3,9,20,null,null,15,7]
8
输出：3

讲解#

如果对二叉树、根节点、左子树、右子树这些概念还不熟，可以先看二叉树的中序遍历里的基础概念。

当前树的最大深度 = max(左子树最大深度, 右子树最大深度) + 1

这个递归可以理解成：函数会不断往下找左子树和右子树，一直找到空节点。找到空节点时，说明这里已经没有节点了，所以返回 0。

然后结果会一层一层往上返回。每往上回到一个真实节点，就在左右子树最大深度的基础上 + 1，表示把当前这个节点也算进去。最后一直返回到最开始的根节点，就得到了整棵树的最大深度。

复杂度#

递归法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)

每个节点都会被访问一次，所以时间复杂度是 O(n)。递归会使用系统调用栈，最坏情况下树退化成链表，递归深度是 n，所以空间复杂度是 O(n)。

代码#

源码#

1
class Solution:
2
    def maxDepth(self, root: "TreeNode") -> int:
3
        if not root:
4
            return 0
5

6
        left_height = self.maxDepth(root.left)
7
        right_height = self.maxDepth(root.right)
8
        return max(left_height, right_height) + 1

测试#

1
from src.python._104_Maximum_Depth_of_Binary_Tree import Solution
2

3

4
class TreeNode:
5
    def __init__(self, val=0, left=None, right=None):
6
        self.val = val
7
        self.left = left
8
        self.right = right
9

10

11
sol = Solution()
12

13
root = TreeNode(3)
14
root.left = TreeNode(9)
15
root.right = TreeNode(20)
16
root.right.left = TreeNode(15)
17
root.right.right = TreeNode(7)
18
assert sol.maxDepth(root) == 3
19

20
assert sol.maxDepth(None) == 0
21
assert sol.maxDepth(TreeNode(1)) == 1
22

23
root = TreeNode(1)
24
root.right = TreeNode(2)
25
assert sol.maxDepth(root) == 2
26

27
print("PASS")

参考资料#

LeetCode 原题：https://leetcode.com/problems/maximum-depth-of-binary-tree/
力扣官方题解：https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/349250/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/

音乐

音乐

题目#

讲解#

复杂度#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录