沅江网站开发_如何开网店拼多多_新公司怎么做网络推广_河北seo推广方案

题目：104. 二叉树的最大深度

难度：简单

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

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

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

一、模式识别：二叉树

求深度 》 层序最好，DFS也可以

二、代码实现

1.递归（DFS）

# 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:if not root:return 0else:return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

2.层序遍历（BFS）

# 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:if not root:return 0ans = 0que = deque([root])while que:ans += 1n = len(que)for _ in range(n):node = que.popleft()if node.left:que.append(node.left)if node.right:que.append(node.right)return ans

3.前中后序（DFS）

前后中后序遍历也可以，就是都写出来太麻烦了，而且都不是最优解