?文档讲解：二叉树的最大深度??二叉树的最小深度??完全二叉树的节点个数
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
思路：
? ? ? ? 求二叉树的深度，其实本质上还是遍历，需要我们找到叶子节点，统计叶子节点的深度即可。
? ? ? ? 因此我们就有多种思路，总结出来就是两种方法，一种是递归法，也就是深度优先搜索，借其进行前中后序遍历即可，这种比较好写，但时间复杂度高，因此本文不做过多阐述。第二种方法是迭代法，也就是广度优先搜索，通常借助队列来实现，下面解释思路。
? ? ? ? 在上一篇文章(Day15)的题目中，我们知道了层序遍历如何做，同时知道了每次同时加入队列或从队列中弹出的节点是同一层的，这样我们每处理一层的节点就把统计的深度加一，初始值为0，那么当我们处理到最后一层时，深度自然也就统计到最大值。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
int depth=0;
queue<TreeNode*> q;
if(root) q.push(root);
while(!q.empty()){
depth++;
TreeNode* cur;
int n=q.size();
while(n--){
cur=q.front();
q.pop();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
return depth;
}
};题目链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/submissions/494720068/
思路：
? ? ? ? N叉树求最大深度，和上一道题目是一模一样的原理。只不过我们在遍历每个节点的儿子时，不再是左右节点，而是一个vector数组，我们针对vector去遍历，判断是否为空加入队列即可，深度的判断逻辑则完全没有改变。本文不再赘述。
核心代码：
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> q;
int depth=0;
if(root) q.push(root);
while(!q.empty()){
depth++;
int n=q.size();
Node* cur;
while(n--){
cur=q.front();
q.pop();
int cnt=cur->children.size();
for(int j=0;j<cnt;j++)
if(cur->children[j]) q.push(cur->children[j]);
}
}
return depth;
}
};题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
思路：
? ? ? ? 求二叉树的最小深度和最大深度，其实区别不大。
? ? ? ? 第一种方法，我们依旧可以利用递归来做，统计到叶子节点，就比较当前深度和记录的深度，取最小值即可。递归结束后的记录深度就是最小深度，输出即可。这样做的时间复杂度无法保证，基本会高，这种写法也简单易懂，就不再过多解释了。
? ? ? ? 第二种方法，用迭代法来做，就仿照上面的104或者559的求最大深度去做就行。那么在做之前，我们首先要知道，最小深度是什么。深度是针对叶子节点来说的，每个叶子节点都有对应深度，最小深度，肯定就是最靠近根节点的叶子节点的深度。那么叶子节点又是什么呢？是没有儿子的节点。了解上述问题，我们就可以解决这道题了。
? ? ? ? 我们依旧采用层序遍历的方式，借助队列来维护。每处理一层的节点，就把深度加一。处理每层的每个节点时，我们会判断它是否有左右儿子，有则加入队列，等待在下层进行处理，如果一个儿子都没有，那么证明它是叶子节点，而且是层数最靠根节点的叶子节点，那么它的深度即我们当前统计到的深度，就是该二叉树的最小深度，我们结束遍历输出这个深度即可。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
int depth=0;
queue<TreeNode*> q;
if(root) q.push(root);
bool flag=false;
while(!q.empty()){
depth++;
TreeNode* cur;
int n=q.size();
while(n--){
cur=q.front();
q.pop();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
if(cur->left==NULL&&cur->right==NULL) flag=true;
if(flag) break;
}
if(flag) break;
}
return depth;
}
};题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/description/
思路：
? ? ? ? 这题我们直接层序遍历，统计节点个数即可。这个方法不论是不是完全二叉树都能做，甚至是N叉树也能做，稍微改下写法就可以。时间复杂度为O(N)，也完全可以接受。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> q;
int ans=0;
if(root) q.push(root);
while(!q.empty()){
int n=q.size();
TreeNode* cur;
while(n--){
cur=q.front();
q.pop();
ans++;
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
}
return ans;
}
};????????今日学习时长3h，题目不算难，尤其有两道昨天就做了。
? ? ? ? 感冒好多了，下午接着看论文准备选题开题。