104.二叉树的最大深度
后序遍历法
class Solution {
public:
int getdepth(TreeNode* node){
if(node == NULL) return 0;
int leftdepth = getdepth(node->left);
int rightdepth = getdepth(node->right);
int depth = 1 + max(leftdepth, rightdepth);
return depth;
}
int maxDepth(TreeNode* root) {
return getdepth(root);
}
};
111. 二叉树的最小深度
后序
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);
}
};
222.完全二叉树的节点数量
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0;
while(left){
left = left->left;
leftDepth++;
}
while(right){
right = right->right;
rightDepth++;
}
if(leftDepth == rightDepth){
return (2 << leftDepth) - 1; // <<为“位运算符”，(2<<1) 相当于2^2，所以leftDepth初始为0
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};