222. Count Complete Tree Nodes

problem description

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

algorithm thought

第一次做这个题的时候，直接没考虑这是个完全二叉树，直接写了个计算二叉树节点数量的函数，直接提交，对了就没管了。

这次做的时候，觉得肯定有更好的办法，因为完全二叉树和普通二叉树相比，多了太多信息。

这里用递归结题，我们知道，计算一个完美二叉树（忘了具体是啥名字了，就是最后一层都是NULL，其他节点都不为NULL）的节点数量很简单，如果有h层，结果就是2^h-1。对于一个完全二叉树，他左子树和右子树肯定有一个是完美二叉树，只要找到这个完美二叉树，就可以直接计算出结果，然后对另一个子树递归调用这个函数。直到节点为NULL

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int h=height(root);
        return h==-1?0:
            height(root->right)==h-1?(1<<h)+countNodes(root->right):
                                        (1<<(h-1))+countNodes(root->left);
    }
    int height(TreeNode* root){
        return root==NULL?-1:height(root->left)+1;  //由于保证是完全二叉树，所以计算高度直接在左边即可
    }
};

algorithm analysis

这个时间复杂度是O(lgn*lgn)，具体时间复杂度分析如下

T(n) = T(n/2) + c1 lgn
       = T(n/4) + c1 lgn + c2 (lgn - 1)
       = ...
       = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
       = O(lgn*lgn)