222. Count Complete Tree Nodes

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

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.

1.首先得到这个完全二叉树的高度h
2.然后判断根节点的右子树的最左节点的高度l与h的关系，
  (1)若l == h - 1，那么左子树为满二叉树

              1
             / \
            2   3
           / \  / \
          4   5 6
  (2)若l = h - 2，那么左子树为完全二叉树
              1
             / \
            2   3
           / \   
          4   5

212ms

class Solution {
public:
    int countNodes(TreeNode* root) {
        int h = height(root);
        if(h < 0)   return 0;
        return height(root->right) == h - 1 ?(1<<h) + countNodes(root->right):(1<<h-1) + countNodes(root->left);
    }
private:
    int height(TreeNode *r){
        return r == NULL ? -1:1+height(r->left);
    }
};

以前的代码:92ms

/**
 * 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) {
        if(root == NULL)
            return 0;

        return bs(root, 1, heightOfCompleteBT(root, 1));
    }
private:
    int heightOfCompleteBT(TreeNode* root, int level){
        while(root){
            level++;
            root = root->left;
        }
        return level - 1;
    }

    int bs(TreeNode *r, int l, int h){
        if(l == h)
            return 1;

        if(heightOfCompleteBT(r->right, l+1) == h){
            return (1<<(h-l)) + bs(r->right, l + 1, h);
        }else
            return (1<<(h - l - 1)) + bs(r->left, l + 1, h);
    }
};