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 2^h nodes inclusive at the last level h.

Example:

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

---

计算完全二叉树的节点个数。如果忽略完全二叉树的性质，像普通二叉树那样进行遍历（先序、中序、后序都可以）统计节点个数，会TLE，所以还是需要用到完全二叉树的性质的。 这里的完全二叉树是指除了最后一层，其他层都是满的，并且最后一层所有节点都是靠左的。具体定义可以看维基百科，下图就是一个完全二叉树的例子： 如果二叉树是满的，比如下面这种，且树的高度是h，则树的节点个数等于$2^h-1$。 那么怎样判断一棵完全二叉树是否是满的呢，只需求一下其极左高度lh和极右高度rh是否相等，如果相等，则是满的，可以用上述公式求解节点数。如果不是满的，则在其左右子树中递归求解节点数，再加上根节点这个节点个数1。 代码如下：

class Solution {
public:
    int countNodes(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = 0, rh = 0;
        TreeNode *l = root, *r = root;
        while (l) {
            ++lh;
            l = l->left;
        }
        while (r) {
            ++rh;
            r = r->right;
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

本代码提交AC，用时82MS。
以上代码还可优化，因为如果知道父亲节点的高度时，其实也就知道了孩子节点的高度了，就是父亲的高度减1，所以在递归时，可以保留高度信息，减少冗余计算。代码如下：

class Solution {
private:
    int height(TreeNode* root, int lh, int rh)
    {
        if (lh == -1) {
            lh = 0;
            TreeNode* l = root;
            while (l) {
                ++lh;
                l = l->left;
            }
        }
        if (rh == -1) {
            rh = 0;
            TreeNode* r = root;
            while (r) {
                ++rh;
                r = r->right;
            }
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return height(root->left, lh – 1, -1) + height(root->right, -1, rh – 1) + 1;
    }
public:
    int countNodes(TreeNode* root) { return height(root, -1, -1); }
};

本代码提交AC，用时55MS，快了一些。