222 - Count Complete Tree Nodes

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

Hide Tags

Tree Binary Search

 

刚开始直接写了个简单的递归，递归计算左右子树，

虽然逻辑上没有问题，但是递归超时

（后来看到有人加了左右相等时直接计算2的幂，可以通过test case）

看题目的提示，是用二分查找，也就是要快速断定最后一个节点的位置。

于是想到就是找root左子的最右边分支，以及右子的最左边分支，

这两个都可以是中点，于是写了一个find函数，找到两个中点，

依照两个中点的深度判断应该选择走左边还是右边。

但是性能并不好，要124ms，把递归调用改成了while循环之后，减少到112ms。

仔细又看了看，实际上并不需要找两个中点，只用右边的就好了，

因为是向左聚拢的嘛，去掉冗余的左边中点，简化判断条件之后，达到了76ms。

/**
* 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)
    {
        TreeNode* p = root;
        int num = 0;
       
        if(root)
        {
            num = 1;
           
            int hh=0;
            while(p)
                hh++, p = p->left; //get height

            if(1==hh)
                return num;
           
            while(root)
            {
                int hr=0;   //find right mid, go right, then keep going left.
                p = root->right;
                while(p)
                    hr++, p = p->left;
       
                //last 2nd level
                if(2==hh)
                    return (hr)?((num<<1) +1):(num<<1); //this is why right mid

                if((hr==(hh-1))&&(root->right))         //this is why right mid
                    num = (num<<1)+1,   root = root->right; //右子索引=parent*2+1
                else if(root->left)
                    num = (num<<1),     root = root->left;  //左子索引=parent*2
                else
                    ;
                hh--;
            }
            //find(root, hh, num);  //recursive call, time-costing.
        }
        return num;
    }

 

/* ----- ONLY FOR Recursive calls ----- */

    void find(TreeNode* root, int hh, int& num)
    {
        int hl=0, hr=0;
       
        TreeNode* p = root->left;
        while(p)
            hl++, p = p->right;

        p = root->right;
        while(p)
            hr++, p = p->left;

        //last 2nd level
        if(2==hh)
        {
            if(hl&&(!hr))
                num = (num<<1);
            else
                num = (num<<1)+1;
            return;
        }
       
        if((hr&&(hr==(hh-1)))&&(root->right))
        {
            num = (num<<1)+1;
            return find(root->right, hh-1, num);
        }
        if(root->left)
        {
            num = (num<<1)+0;
            return find(root->left, hh-1, num);
        }
        return;
    }

/* ----- this solution works but takes too much time  ----- */
    int countNodes_timeout_solution(TreeNode* root) {
        int rst = 0;
        if(root)
        {
            if(root->left)
                rst += countNodes(root->left);
            if(root->right)
                rst += countNodes(root->right);

            rst += 1;
        }
        return rst;
    }
};

发在讨论区了。