LeetCode 222 Count Complete Tree Nodes
概述
https://leetcode.com/problems/count-complete-tree-nodes/
时间复杂度要求 O(n)
直接法
不管完全二叉树的条件，直接计数。
每个节点都调用一次函数，因此时间复杂度 O(n)。
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
利用完全二叉树的性质优化
https://labuladong.gitee.io/algo/2/18/32/
一棵完全二叉树的两棵子树，至少有一棵是满二叉树。
时间复杂度 O(logn * logn)，因为函数本身是 logn（树的高度）。
每次函数调用时，两个子调用其中一个立刻返回，所以一共调用了树的高度次。
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
int ld = 0;
auto l = root;
while (l) {
l = l->left;
ld ++;
}
int rd = 0;
auto r = root;
while (r) {
r = r->right;
rd ++;
}
if (ld == rd) { // full tree
return int(pow(2, ld)) - 1;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};