今日学习的文章和视频链接
https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=8272bd48fee17396a4a1746c256ab0ae
104 二叉树的最大深度
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100
我的思路
用递归，但是什么顺序没想清楚
题目分析
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
先用后序遍历（左右中）来计算树的高度。
确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
代码如下：
int getdepth(TreeNode* node)
确定终止条件：如果为空节点的话，就返回0，表示高度为0。
代码如下：
if (node == NULL) return 0;
确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
代码如下：
int leftdepth = getdepth(node->left); // 左
int rightdepth = getdepth(node->right); // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;
acm模式代码
int main() {
// 创建二叉树的节点
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 创建Solution实例
Solution solution;
// 计算并打印最大深度
std::cout << "Maximum depth of the binary tree is: " << solution.maxDepth(root) << std::endl;
// TODO: 释放分配的内存（在实际应用中很重要）
// ...
return 0;
}
111二叉树最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000
我的想法
直接和上题一样，返回min+1
题目分析
本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。
题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
递归法：
递归三部曲：
确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是int类型的深度。
代码如下：
int getDepth(TreeNode* node)
确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0。
代码如下：
if (node == NULL) return 0;
确定单层递归的逻辑
这块和求最大深度可就不一样了，一些同学可能会写如下代码：
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;
如果这么求的话，没有左孩子的分支会算为最短深度。
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
acm模式代码
#include <iostream>
#include <algorithm>
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
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 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->left != nullptr && node->left == nullptr) {
return 1 + leftdepth;
}
int depth = 1 + std::min(leftdepth, rightdepth);
return depth;
}
int minDepth(TreeNode* root) {
return getdepth(root);
}
};
int main() {
// 创建二叉树的节点
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
// root->left->right = new TreeNode(5);
// 创建Solution实例
Solution solution;
// 计算并打印最小深度
std::cout << "Minimum depth of the binary tree is: " << solution.minDepth(root) << std::endl;
// TODO: 释放分配的内存（在实际应用中很重要）
// ...
return 0;
}
222完全二叉树的节点个数
题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
我的想法
后序遍历统计节点个数
题目分析
普通二叉树可以求解，时间复杂度为n
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。文章来源：https://www.toymoban.com/news/detail-793147.html
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树文章来源地址https://www.toymoban.com/news/detail-793147.html
acm模式代码
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
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) {
//第二步 判断终止条件
if (root == nullptr) {
return 0;
}
int countleft = 0;
int countright= 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
while(left) {
left = left->left;
countleft ++;
}
while (right) {
right = right->right;
countright ++;
}
if (countleft == countright) {
return (2 << countleft) - 1;
}
int leftnodes = countNodes(root->left);
int rightnodes= countNodes(root->right);
int sum = leftnodes + rightnodes + 1;
return sum;
}
};
int main() {
// 创建二叉树的节点
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
// 创建Solution实例
Solution solution;
// 计算并打印节点总数
std::cout << "Total number of nodes in the binary tree is: " << solution.countNodes(root) << std::endl;
// TODO: 释放分配的内存（在实际应用中很重要）
// ...
return 0;
}
到了这里，关于算法训练day16Leetcode104二叉树最大深度111二叉树最小深度222完全二叉树的节点个数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
