Easy short c++ recursive solution


  • 153
    V
    class Solution {
    
    public:
    
        int countNodes(TreeNode* root) {
    
            if(!root) return 0;
    
            int hl=0, hr=0;
    
            TreeNode *l=root, *r=root;
    
            while(l) {hl++;l=l->left;}
    
            while(r) {hr++;r=r->right;}
    
            if(hl==hr) return pow(2,hl)-1;
    
            return 1+countNodes(root->left)+countNodes(root->right);
    
        }
    
    };

  • 3
    L

    nice solution. is there anyone who can tell how to calculate the time complexity of this one?


  • 3
    V

    There are at most lgn divisions, and lgn to calculate height within each division. So lgn * lgn


  • 30
    M

    Let n be the total number of the tree. It is likely that you will get a child tree as a perfect binary tree and a non-perfect binary tree (T(n/2)) at each level.

    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)   

  • 2
    R

    Using a extra function,the height of left branch could be calculate only once.below is my c solution

    int recursiveCountWithHeight(struct TreeNode* root,int height) {
    	if(NULL==root) return 0;
    
    	struct TreeNode *p=root;
    	int r_h=0;
    	while(NULL!=p){
    		++r_h;
    		p=p->right;
    	}
    
    	if(height==r_h){
    		return pow(2,height)-1;
    	}else{
    		return 1+recursiveCountWithHeight(root->left,height-1)
    			+recursiveCountWithHeight(root->right,height-1);
    	}
    }
    
    int countNodes(struct TreeNode* root) {
    	if(NULL==root) return 0;
    
    	struct TreeNode *p=root;
    	int height=0;
    	// left height only needs to be calculated once
    	while(NULL!=p){
    		++height;
    		p=p->left;
    	}
    
    	return recursiveCountWithHeight(root,height);
    }

  • 0

    How "likely" is it?


  • 1
    L

    Does this solution work? You will need to re-calculate the left-height of right sub-tree right?

    Perhaps should be

    return 1+recursiveCountWithHeight(root->left, height-1) + countNodes(root->right);


  • 0
    R

    it is accepted.but on second thoughts I think u r right about it.when the right sub-tree is a complete tree and its height is one short than the left one,my solution will cause the calculation of the right part recursive needlessly,though it gives out the right answer,but the efficiency is reduced with no good reason.after modified the runtime of OJ is decrease from 74ms to 64 ms. thanks for your advice!


  • -2
    J
    An improved method
    pair<int,int> CountCompleteNodes(TreeNode* root)
    {
        if(!root)
        {
            return make_pair(0,0);
        }        
        int LeftLevel = 1;
        auto pLeft = root->left;
        while(pLeft)
        {
            LeftLevel++;
            pLeft = pLeft->left;
        }
        int RightLevel = 1;
        auto pRight = root->right;
        while(pRight)
        {
            RightLevel++;
            pRight = pRight->right;
        }
        if(LeftLevel == RightLevel)
        {
            return make_pair(pow(2, LeftLevel)-1, LeftLevel);
        }        
        auto RightNode = CountCompleteNodes(root->right);
        if(LeftLevel == RightNode.second)
        {
            return make_pair(pow(2, LeftLevel-1)-1+RightNode.first, LeftLevel);
        }else
        {
            auto LeftNode = CountCompleteNodes(root->left);
            return make_pair(1+LeftNode.first+RightNode.first, LeftLevel);
        }
    }

  • 0

    How is that an improvement? And where is the countNodes function?


  • 0
    O

    you either get two perfect binary tree or a perfect + a non-perfect. So a perfect + a non-perfect is already the worst case

    as for how likely? (I could be wrong), there are possible (0 ~ 2^h) nodes in the bottom level. The only two cases that gives a perfect binary tree is 0, 2^h. So probability is (2^h + 1 - 2) / (2^h + 1)


  • 0

    1+countNodes(root->left)+countNodes(root->right); Nice solution, Thank you!


  • 1
    C

    if pow(2,hl) is changed to be (1<<hl), the run time would decline from 360ms to 170 ms approximately.


  • 0
    Y

    1 + 2 + .. + h ~ O(h^2), where h = log(n)


  • 0
    V

    Wait. Should the recursion be:
    T(n) = 2T(n/2) + c1 lgn ?
    Am I correct? If so,
    T(n) = 2^level * T(1) + c1 [lgn + lg(n-1) + ... + 1]
    = n+ lgn
    lgn = O(n)


  • 0
    Y

    @Chauncey thanks for the improvement.


  • 0
    Y

    @vanbasten23 no,in best case, left depth==right depth, so take constant time to calculate.
    in the worst case, one of the left and right tree is a full tree, so T(n)=T(n/2)+....;


  • 0
    M

    I think as far likely is concerned, the probability is 1, because there is always a child tree which is complete at every level. There could be two child trees as full or just one.


  • 0
    J

    @redace85 I think this code is exactly the same but why does it TLE?

    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        TreeNode* l = root;
        int hl = 0;
        while(l){
            l = l->left; hl++;
        }
        return countWithLeftHeight(root,hl);
    }
    
    int countWithLeftHeight(TreeNode* root, int hl){
        if(root == NULL) return 0;
        TreeNode* r = root;
        int hr = 0;
        while(r){
            r = r->right; hr++;
        }
        if(hl == hr){
            return (1<<hl) - 1;
        }
        return 1 + countWithLeftHeight(root->left,hl-1) + countWithLeftHeight(root->right,hl-1);
    }

  • 0

    nice solution~ i think height can be re-used when countNodes(root->left) like:

    class Solution(object):
        def left_height(self, root):
            height = 0
            while root is not None:
                root = root.left
                height += 1
            return height
    
        def right_height(self, root):
            height = 0
            while root is not None:
                root = root.right
                height += 1
            return height
    
        def count(self, root, left, right):
            if left == -1:
                left = self.left_height(root)
            if right == -1:
                right = self.right_height(root)
            if left == right:
                return 2**right-1
            else:
                return 1+self.count(root.left, left-1, -1)+self.count(root.right, -1, right-1)
    
        def countNodes(self, root):
            return self.count(root, -1, -1)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.