LeetCode104. 二叉树的最大深度
题目链接：104. 二叉树的最大深度
初次尝试
直接看题解学习思路。
看完代码随想录后的想法
本题使用的是二叉树的后序遍历，实际上是在求根节点的高度，这是因为根节点的高度就是最大深度，高度和深度的定义如下。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL) return 0;
int leftheight = getHeight(node -> left);
int rightheight = getHeight(node -> right);
return max(leftheight, rightheight) + 1;
}
int maxDepth(TreeNode* root) {
return getHeight(root);
}
};
LeetCode559. n叉树的最大深度
题目链接：559. n叉树的最大深度
初次尝试
直接看题解学习思路。
看完代码随想录后的想法
和二叉树的思路一样，一遍ac。
class Solution {
public:
int getHeight(Node* node) {
if (node == NULL) return 0;
int max_height = 0;
for (auto iter = node -> children.begin(); iter != node -> children.end(); iter++) {
max_height = max(max_height, getHeight(*iter));
}
return max_height + 1;
}
int maxDepth(Node* root) {
return getHeight(root);
}
};
LeetCode111. 二叉树的最小深度
题目链接：111. 二叉树的最小深度
初次尝试
使用了后序递归法，和最大深度的思路是差不多的，只是需要注意在遍历一个子树空一个子树不空的节点时，递归函数需要返回不空的子树的高度而不是空子树的高度0。
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL) return 0;
int leftHeight = getHeight(node -> left);
int rightHeight = getHeight(node -> right);
if (leftHeight == 0 || rightHeight == 0) return max(leftHeight, rightHeight) + 1;
else return min(leftHeight, rightHeight) + 1;
}
int minDepth(TreeNode* root) {
return getHeight(root);
}
};
看完代码随想录后的想法
思路是一样的，题解中对于最小深度和最大深度区别的解释更加清晰：
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
注意是根节点到叶子节点的最短路径，左右孩子都为空的节点才是叶子节点，一空一不空的节点不能算作叶子节点，所以一空一不空的节点高度不能为1。
LeetCode111. 二叉树的最小深度
题目链接：111. 二叉树的最小深度
初次尝试
使用了后序递归法，和最大深度的思路是差不多的，只是需要注意在遍历一个子树空一个子树不空的节点时，递归函数需要返回不空的子树的高度而不是空子树的高度0。
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == NULL) return 0;
int leftHeight = getHeight(node -> left);
int rightHeight = getHeight(node -> right);
if (leftHeight == 0 || rightHeight == 0) return max(leftHeight, rightHeight) + 1;
else return min(leftHeight, rightHeight) + 1;
}
int minDepth(TreeNode* root) {
return getHeight(root);
}
};
看完代码随想录后的想法
思路是一样的，题解中对于最小深度和最大深度区别的解释更加清晰：
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
注意是根节点到叶子节点的最短路径，左右孩子都为空的节点才是叶子节点，一空一不空的节点不能算作叶子节点，所以一空一不空的节点高度不能为1。
LeetCode222. 完全二叉树的节点个数
题目链接：222. 完全二叉树的节点个数
初次尝试
使用了后序递归法，和前几题的思路是一样的。
class Solution {
public:
int getNumofNodes(TreeNode* node) {
if (node == NULL) return 0;
int left_num = getNumofNodes(node -> left);
int right_num = getNumofNodes(node -> right);
return left_num + right_num + 1;
}
int countNodes(TreeNode* root) {
return getNumofNodes(root);
}
};
看完代码随想录后的想法
上面的思路是适用于任何二叉树的，时间复杂度为O(n)。对于完全二叉树，可以利用它的性质，对递归函数返回条件做一些优化，即每次递归先通过向左向右遍历深度是否相等，来判断以该节点为根节点的子树是否是满二叉树，如果是满二叉树则可以通过将遍历深度代入公式直接求出该子树的节点数返回，由此减少递归次数，时间复杂度为O(logn)。
class Solution {
public:
int getNumofNodes(TreeNode* node) {
if (node == NULL) return 0;
TreeNode* left = node -> left;
TreeNode* right = node -> right;
int left_depth = 0, right_depth = 0;
while (left) {
left_depth++;
left = left -> left;
}
while (right) {
right_depth++;
right = right -> right;
}
if (left_depth == right_depth) return (2 << left_depth) - 1;
return getNumofNodes(node -> left) + getNumofNodes(node -> right) + 1;
}
int countNodes(TreeNode* root) {
return getNumofNodes(root);
}
};