LeetCode 222 Count Complete Tree Nodes
https://leetcode.com/problems/count-complete-tree-nodes/
当做普通二叉树进行处理
最简单的暴力方法,无视完全二叉树的条件,直接当做普通二叉树进行处理。
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
因为对于每个节点我们都遍历了一遍,复杂度为 O(N)
考虑到完全二叉树至少有一个子树是满二叉树
class Solution {
public:
int countNodes(TreeNode* root) {
TreeNode *left = root, *right = root;
int leftHeight = 0, rightHeight = 0;
while(left!=nullptr) {
++leftHeight; // Notice this is not left subtree's height
left = left->left;
}
while(right!=nullptr) {
++rightHeight;
right = right->right;
}
if(leftHeight == rightHeight) { // It's a perfect binary tree.
return pow(2, leftHeight) - 1;
} else {
return countNodes(root->left) + countNodes(root->right) + 1;
}
}
};
while 循环的复杂度为树的高度即 O(log n)
然后递归了多少次呢?实际上由于其中一个子树为满二叉树,处理该子树时递归不再继续下去, 也就是说在树的每一层,我们最多只选择其中一个分支递归下去,则递归了树的高度即 log n 次, 则复杂度为 O(logN*logN)