目录
Leetcode 104.二叉树的最大深度
Leetcode 559.n叉树的最大深度
Leetcode 111.二叉树的最小深度
Leetcode 222.完全二叉树的节点个数
Leetcode 104.二叉树的最大深度
题目链接：Leetcode 104.二叉树的最大深度
题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
思路：前序遍历通常用于求深度，后序遍历通常用于求高度。这么来看这道题似乎只能用前序遍历了，不过我们知道根节点的高度就是二叉树的最大深度，因此两种遍历方式都可以。除此之外，层序遍历对于本题也是适合的，我们只需要基于层序遍历的模板，添加统计层数的行为就可以了。
代码如下：（递归法——前序遍历）
class Solution {
public:
int result;
void getdepth(TreeNode* node, int depth) {
result = max(result, depth);
if (node->left == nullptr && node->right == nullptr)//中
return;
if (node->left)//左
getdepth(node->left, depth + 1);
if (node->right)//右
getdepth(node->right, depth + 1);
return;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == nullptr)
return result;
getdepth(root, 1);
return result;
}
};（递归法——后序遍历）
class Solution {
public:
int getdepth(TreeNode* root) {
if (root == nullptr)
return 0;
int leftdepth = getdepth(root->left);
int rightdepth = getdepth(root->right);
//这里加1是因为要算上当前中间节点那一层
int depth = 1 + max(leftdepth, rightdepth);
return depth;
}
int maxDepth(TreeNode* root) { return getdepth(root); }
};
（迭代法——层序遍历）
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
}
}
return depth;
}
};Leetcode 559.n叉树的最大深度
题目链接：Leetcode 559.n叉树的最大深度
题目描述：给定一个 n 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
思路：这道题和上道题Leetcode 104.二叉树的最大深度几乎没什么区别，两道题的关键在于理解根节点的高度等于n叉树的最大深度。
代码如下：（递归法）
class Solution {
public:
int maxDepth(Node* root) {
if (root == nullptr)
return 0;
int depth = 0;
for (int i = 0; i < root->children.size(); i++) {
depth = max(depth, maxDepth(root->children[i]));
}
return depth + 1;
}
};（迭代法）
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> que;
int depth = 0;
if (root != nullptr)
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
for (int j = 0; j < node->children.size(); j++) {
if (node->children[j])
que.push(node->children[j]);
}
}
}
return depth;
}
};Leetcode 111.二叉树的最小深度
题目链接：Leetcode 111.二叉树的最小深度
题目描述：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
思路：本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。但一定要注意题干对最小深度的描述：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。什么是叶子节点？左右孩子都为空的时候才是。如果左右孩子中只有一个孩子为空，则找深度时返回非空孩子的深度+1（而不是看最小深度）；如果左右孩子都为空，说明是叶子节点，返回左右孩子的最小深度+1。
注：上述图片来源于《代码随想录》
代码如下：（递归法——前序遍历）
class Solution {
public:
int result;
void getDepth(TreeNode* node, int depth) {
if (node == nullptr)
return;
//中，判断是否是叶子节点
if (node->left == nullptr && node->right == nullptr) {
result = min(result, depth);
}
if (node->left) {//左
getDepth(node->left, depth + 1);
}
if (node->right) {//右
getDepth(node->right, depth + 1);
}
return;
}
int minDepth(TreeNode* root) {
if (root == nullptr)
return 0;
result=INT_MAX;
getDepth(root, 1);
return result;
}
};（递归法——后序遍历）
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == nullptr)
return 0;
int leftdepth = getDepth(node->left); //左
int rightdepth = getDepth(node->right); //右
//中
if (node->left == nullptr && node->right != nullptr) {
return 1 + rightdepth;
}
if (node->right == nullptr && node->left != nullptr) {
return 1 + leftdepth;
}
return 1 + min(leftdepth, rightdepth);
}
int minDepth(TreeNode* root) { return getDepth(root); }
};（迭代法——层序遍历）
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr)
return 0;
queue<TreeNode*> que;
int depth = 0;
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++; //记录最小深度
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
if (!node->left && !node->right) //只有左右孩子都为空时，才返回
return depth;
}
}
return depth;
}
};Leetcode 222.完全二叉树的节点个数
题目链接：Leetcode 222.完全二叉树的节点个数
题目描述：给出一个完全二叉树，求出该树的节点个数。
思路：统计节点个数，遍历计数就好了，很容易解决本题。
代码如下：（递归法）
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
int leftnum = countNodes(root->left);
int rightnum = countNodes(root->right);
int result = leftnum + rightnum + 1;
return result;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(log n)
（迭代法）
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
queue<TreeNode*> que;
que.push(root);
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
result++;
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
}
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
不过观察到题目给的是完全二叉树，因此可以利用它的性质来优化。在此之前需要了解完全二叉树和满二叉树的概念：可以看这里。在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况，（1）就是满二叉树（2）最后一层叶子节点没有满。
对于（1），可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于（2），分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
接下来思考如何判断是否是满二叉树？在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。因此只需要递归判断一个节点的左右孩子深度是否相等就好了。
代码如下：（利用完全二叉树的性质优化）
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftdepth = 1, rightdepth = 1;//一个节点深度为1，
while (left) {
left = left->left;
leftdepth++;
}
while (right) {
right = right->right;
rightdepth++;
}
if (leftdepth == rightdepth) {
return pow(2, leftdepth) - 1;
}
return countNodes(root->left) + countNodes(root->right) + 1;//递归调用下一层
}
};- 时间复杂度：O(log n × log n)
- 空间复杂度：O(log n)
总结：做了这些有关二叉树的题，发现很多都是基于二叉树的遍历模板稍加修改就可以解决的题目，因此打牢基础很重要！
最后，如果文章有错误，请在评论区或私信指出，让我们共同进步！
![【C++入门到精通】特殊类的设计 |只能在堆 ( 栈 ) 上创建对象的类 |禁止拷贝和继承的类 [ C++入门 ]](https://img-blog.csdnimg.cn/direct/32ed20b44d704746a77da19b16d060e5.jpeg)
