【剑指 Offer 55 - I. 二叉树的深度】
题目描述：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
- 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
- 说明: 叶子节点是指没有子节点的节点。
示例：
- 示例1：
- 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
- 返回它的最大深度 3 。
- 示例2：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
- 提示：
1 <= 数组长度 <= 50000
前提知识：
- 树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）。
常见的 DFS ： 先序遍历(中左右)、中序遍历（左中右）、后序遍历（左右中）；
常见的 BFS ： 层序遍历（即按层遍历）。
解析思路1：后序遍历（DFS）->递归 ：max（左、右子树层数）+1
-
基于 树 后序遍历 的 DFS 和 层序遍历 的 BFS 。
- 算法流程示意图：
- 同理：
代码（cpp）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int leftDepth = maxDepth(root->left); //左子树深度
int rightDepth = maxDepth(root->right); //右子树深
return max(leftDepth, rightDepth)+1 ; //当前节点的深度
}
};
代码（python3）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
复杂度分析：
- 时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
- 空间复杂度 O(N) ： 最差情况下（当树退化为链表时），递归深度可达到 N 。
解析思路2：层序遍历（BFS）
-
广度优先搜索（BFS）
-
树的层序遍历 / 广度优先搜索往往利用 队列 实现。
-
核心问题： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。
-
算法流程：
代码（cpp）
注意 遍历每层时候，利用队列存放、遍历删除当前层节点的代码过程
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
// private:
// int res = 0;
public:
int maxDepth(TreeNode* root) {
if (root ==NULL) return 0;
queue<TreeNode*> q; //创建空队列q
q.push(root); //将root推入队列q
int res = 0;
while(!q.empty()){
++ res;
for(int i=q.size();i>0;i--){ //遍历队列q中的当前层节点
// TreeNode* node = q.front();
auto node = q.front();
q.pop(); // 删除队列中当前层节点
if (node->left ) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
};
代码（python3）
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
queue, res = [root], 0
while queue:
tmp = []
for node in queue:
if node.left: tmp.append(node.left)
if node.right: tmp.append(node.right)
queue = tmp
res += 1
return res
复杂度分析：
- 时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
- 空间复杂度 O(N) ： 最差情况下**（当树平衡时）**，队列 queue 同时存储 N/2 个节点。