104. 二叉树的最大深度
文章：代码随想录 (programmercarl.com)
视频：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度_哔哩哔哩_bilibili
递归中，后序遍历求头结点的最大高度 = 求二叉树的最大深度，用先序遍历求深度代码会很麻烦
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL)
{
return 0;
}
int leftHeight = getHeight(node->left);//左 获取左子树高度
int rightHeight = getHeight(node->right);//右 获取右子树高度
int height = 1 + max(leftHeight, rightHeight);//中 当前最大高度=1+左右子树的最大高度
return height;
}
int maxDepth(TreeNode* root) {
return getHeight(root);
}
};
111. 二叉树的最小深度
文章：代码随想录 (programmercarl.com)
视频：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度_哔哩哔哩_bilibili
思路：
本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。
以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。
本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右
// 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
559. N 叉树的最大深度
文章：代码随想录 (programmercarl.com)
class Solution {
public:
int maxDepth(Node* node) {
if (node == NULL)
{
return 0;
}
int depth = 0;
for (int i = 0; i < node->children.size(); i++)
{
//递归比较每一个子树的最大高度
depth = max(depth, maxDepth(node->children[i]));
}
return depth + 1; //子树的最大高度+1 = 根节点的最大高度 = 二叉树的最大深度
}
};
//迭代法：层序遍历模板
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> que;
if (root != NULL)
{
que.push(root);
}
int maxDepth = 0;
while (!que.empty())
{
int size = que.size();
maxDepth++;
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] != NULL)
{
que.push(node->children[j]);
}
}
}
}
return maxDepth;
}
};
222. 完全二叉树的节点个数
文章：代码随想录 (programmercarl.com)
思路：
那么只要模板少做改动，加一个变量result，统计节点数量就可以了
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL)
{
que.push(root);
}
int result = 0;
while (!que.empty())
{
int size = que.size();
while (size--)
{
TreeNode* node = que.front();
que.pop();
result++;
if (node->left != NULL)
{
que.push(node->left);
}
if (node->right != NULL)
{
que.push(node->right);
}
}
}
return result;
}
};
class Solution {
public:
int getNodesNum(TreeNode* node) {
if (node == NULL)
{
return 0;
}
int leftNum = getNodesNum(node->left);
int rightNum = getNodesNum(node->right);
int treeNode = leftNum + rightNum + 1;
return treeNode;
}
int countNodes(TreeNode* root) {
return getNodesNum(root);
}
};