解题思路
1.题目描述
1.1 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例1：
输入：root=[3,9,20,null,null,15,7]
输出：depth=3
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
1.2 n叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree
示例1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3
1.2 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
2.题目分析与解答
2.1 二叉树的最大深度
2.1.1 深度优先思想
通过求出树的各个子树的最大深度，取其最大值，然后加一，就是树的最大深度。代码如下
//深度优先递归解法
class Solution {
public:
int maxDepth(TreeNode* root) {
//空节点高度为0
if(root == nullptr) return 0;
//否则就是左右子树的高度的较大值+1
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
2.1.2 广度优先思想
要求树的深度，我们同样可以采用对树进行层次遍历，然后记录其层数，当遍历完，也就到了树的最后一层。也就是我们要求的最大深度。
// 层次遍历解法
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int res = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
size_t size = que.size();
// 只有每一层的节点全部处理完才进行层数叠加操作
// while(size--){
TreeNode *cur = que.front();
que.pop();
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}
res++;
}
return res;
}
};
2.2 n叉树的最大深度
求n叉树的最大深度和二叉树的最大深度原理相同，不过由于n叉树的子节点是一个vector，所以我们在遍历时要确保可以处理到每一个子节点。这一点可以通过增加一个for循环来实现。
2.2.1 深度优先——递归
//深度优先——递归写法
class Solution {
public:
int maxDepth(Node* root) {
if(root == nullptr) return 0;
// 根不为空 初始化深度为1
int deep = 0;
for(auto c:root->children){
//注意这里不要使用deep = maxDepth(c) > deep? maxDepth(c):deep;
// 因为这样会导致递归次数多了一倍，造成很大的时间资源浪费
int d = maxDepth(c);
deep = d > deep? d:deep;
}
return deep+1;
}
};
2.2.2广度优先——层次遍历
//广度优先处理——层次遍历求深度
// 基本上是模仿二叉树的遍历实现的，只是在下面的103行处理有特点
class Solution {
public:
int maxDepth(Node* root) {
if(root == nullptr) return 0;
// 初始化层次遍历辅助队列
queue<Node*> que;
// 根节点入队
que.push(root);
// 预设深度depth为0，因为节点是在出队的时候处理
int depth = 0;
// 队列不为空则说明未处理完
while(!que.empty()){
// q_size是当前节点所在的层的节点数，确保按层进行处理
size_t q_size = que.size();
Node* node ;
while(q_size--){
node = que.front();
que.pop();
// 当前处理的节点的子结点个数，这也是与二叉树的区别
int n_size = node->children.size();
for(int i=0;i<n_size;i++){
que.push(node->children[i]);
}
}
// 处理完一层，深度加一
depth++;
}
return depth;
}
};
2.3 二叉树的最小深度
求最小深度的时候有一个容易混淆的地方，那就是**最小深度是从根节点到最近叶子节点的最短路径上的节点数量。**注意这里必须是根节点到叶子节点的最短路径。我们看修改一下题目中的例子就清楚了，看下面的例子。虽然此时我们第一印象会觉得最小深度的是1，但是并不是这样的，因为左子树是空树，所以我们需要在右子树中找到有着最短路径的叶节点。我们会发现叶节点是15或者7。所以此时的最小深度就是3。
2.3.1 深度优先——递归
根据上面的分析，我们设置的递归的单层逻辑与求最大深度的有了很大的不同。只有当当前节点的左右子树均为空或者均不为空我们才考虑在这两个子树里面寻找满足条件的叶节点。
当左右子树有一颗为空，那么就只能在另外一棵子树中寻找符合条件的最短路径。
class Solution {
public:
int minDepth(TreeNode* root) {
// 根节点为空直接返回
if(root == nullptr) return 0;
// 分别求出左右子树的最小深度
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
// 处理左右子树其中一个为空的情况
// 其中一个为空则根据另一个求最小深度
if(root->left && root->right == nullptr)
return 1+leftDepth;
if(root->left == nullptr && root->right)
return 1+rightDepth;
// 两个子树同时为空或者同时不为空的时候
// 只有两棵子树同时为空才是满足条件的最小深度的叶节点
int res = 1+min(leftDepth,rightDepth);
return res;
}
};
2.3.2 广度优先——层次遍历
使用层次遍历求解最小深度类似最大深度的求法，此题也可以使用层次遍历来实现。
但是此时的层次遍历有了提前终止条件，那就是碰到一个叶节点。碰到叶节点意味着当前最小深度已经找到。
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
queue<TreeNode*> que;
que.push(root);
// 最小深度初始化
int depth = 0;
// 与普通层次遍历类似
while(!que.empty()){
TreeNode* node;
size_t size = que.size();
depth++;
while(size--){
node = que.front();
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
// 如果碰到叶节点，则说明是最小深度，可以提前返回深度
if(node->left == nullptr && node->right == nullptr)
return depth;
}
}
//
return depth;
}
};
总结：树的各种遍历需要熟记理解