代码随想录算法训练营第12天|104. 二叉树的最大深度、111. 二叉树的最小深度、 222. 完全二叉树的节点个数
代码随想录算法训练营第12天|104. 二叉树的最大深度、111. 二叉树的最小深度、 222. 完全二叉树的节点个数
104. 二叉树的最大深度
题目链接
提交代码（迭代法）
class Solution {
public:int maxDepth(TreeNode* root) {int depth = 0;queue<TreeNode*> que;if(root == nullptr)return 0;que.push(root);while(!que.empty()){depth++;int size = que.size();while(size--){TreeNode* node = que.front();que.pop();if(node -> left != nullptr)que.push(node -> left);if(node -> right != nullptr)que.push(node -> right);}}return depth;}
};
提交代码（递归法）
class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;return 1 + max(maxDepth(root -> left), maxDepth(root -> right));}
};
111. 二叉树的最小深度
题目链接
提交代码（迭代法）
class Solution {
public:int minDepth(TreeNode* root) {int depth = 0;queue<TreeNode*> que;if(root == nullptr)return depth;que.push(root);while(!que.empty()){depth++;int size = que.size();while(size--){TreeNode* node = que.front();que.pop();if(node -> left != nullptr)que.push(node -> left);if(node -> right != nullptr)que.push(node -> right);if(node -> left == nullptr && node -> right == nullptr)return depth;}}return depth;}
};
提交代码（递归法）
class Solution {
public:int minDepth(TreeNode* root) {if(root == nullptr) return 0;int leftDepth = minDepth(root -> left);int rightDepth = minDepth(root -> right);if(root -> left == nullptr && root -> right == nullptr) return 1;else if(root -> left == nullptr && root -> right != nullptr) return 1 + rightDepth;else if(root -> left != nullptr && root -> right == nullptr) return 1 + leftDepth;else return 1 + min(leftDepth, rightDepth);}
};
222. 完全二叉树的节点个数
题目链接
提交代码（递归）
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;return 1 + countNodes(root -> left) + countNodes(root -> right);}
};
提交代码（用完全二叉树特性，找满二叉树）
class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;int leftDepth = 0; int rightDepth = 0;TreeNode* left = root -> left;TreeNode* right = root -> right;while(left){left = left -> left;leftDepth++;}while(right){right = right -> right;rightDepth++;}if(leftDepth == rightDepth)return pow(2, leftDepth + 1) - 1;return 1 + countNodes(root -> left) + countNodes(root -> right);}
};
提交代码（官方题解，二分查找 + 位运算）
总结
日期： 2023 年 3 月 30 日
学习时长： 0 h 30 m
难度：★\\bigstar★
累计完成题目数量： 48
距离目标还有数量： 252
小结：
- 前两道题的迭代法都可以用二叉树的层序遍历解决
- 第三题直接用递归的空间复杂度是logn
- 第三题官方题解没看，看不进去了