222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

如果是一個完整的Binary Tree，所有level的節點填滿，高度是h的話，那總共有2^h - 1個nodes。第一個recursion的方法是用兩個TreeNode pointers分別從一個node開始往左和往右下去，如果最後發現這兩邊走到底的深度一樣，那麼以這個節點開始的subtree就是一個填滿的binary tree，可以直接用上述數學式得到所有nodes數量。

int countNodes(TreeNode* root) { // time: O(n^2); space: O(n)
    int left_h = 0, right_h = 0;
    TreeNode *left_ptr = root, *right_ptr = root;
    while (left_ptr) {
        ++left_h;
        left_ptr = left_ptr->left;
    }
    while (right_ptr) {
        ++right_h;
        right_ptr = right_ptr->right;
    }
    if (left_h == right_h) return pow(2, left_h) - 1;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int leftHeight(TreeNode* root) {
    if (!root) return 0;
    return 1 + leftHeight(root->left);
}
int rightHeight(TreeNode* root) {
    if (!root) return 0;
    return 1 + rightHeight(root->right);
}
int countNodes(TreeNode* root) { // time: O(n^2); space: O(n)
    int left_h = leftHeight(root), right_h = rightHeight(root);
    if (left_h == right_h) return pow(2, left_h) - 1;
    return countNodes(root->left) + countNodes(root->right) + 1;
}