C++ recursive and iterative solution O(logn^2)


  • 0
    M

    Recursive Method:

    1. Check if current node is the root of a full BT. If yes, number of nodes = pow(2,height) -1.
    2. Calculate number of nodes in both left and right subtrees. Return sum + 1.
    class Solution {
    public:
        int countNodes(TreeNode* root) {
            
            if(!root) return 0;
            int hl = 0, hr = 0;
            TreeNode *lnode = root, *rnode = root;
            while(lnode){ lnode = lnode->left; hl++; }
            while(rnode){ rnode = rnode->right; hr++; }
            if(hl == hr) return pow(2, hl) - 1;
            else return countNodes(root->left) + countNodes(root->right) + 1;
    
            }
    }
    

    Iterative Method:

    Find the last node of the tree. By calculating the height of left and right subtree, we can decide the last node is in the left or right.

    class Solution {
    public:
        int countNodes(TreeNode* root) {
      
          // Iterative - Find the last node of the tree
            if(!root) return 0;
            
            int hl = leftheight(root), hr = rightheight(root), ans = 1;
            int hll = hl-1, hlr = rightheight(root->left), hrl = leftheight(root->right), hrr = hr-1;
            
            while(root->left){
                // Three cases to move to the right subtree:
                // Case 1: I am the root of a full BT
                // Case 2: Only the left subtree is a full BT
                // Case 3: Both left and right subtrees are full BTs and have same height
                if((hl == hr) ||
                    (hll == hlr && hrl == hrr && hll == hrr) ||    
                    (hll == hlr && hrl != hrr)){                
                    root = root->right;
                    ans = ans * 2 + 1;
                    // cout<<"move right, ans = "<<ans<<endl;
                    hr = hrr; hrr = rightheight(root->right); hrl = leftheight(root->right);
                    hl = hrl; hll = leftheight(root->left);   hlr = rightheight(root->left);
                }
                // Two cases to move to the right subtree:
                // Case 1: Only the right subtree is a full BT
                // Case 2: Both subtrees are full BTs but have diff height
                else if((hll == hlr && hrl == hrr && hll != hrr) || 
                    (hll != hlr && hrl == hrr)){
                    root = root->left;
                    ans = ans * 2;
                    hr = hlr; hrr = rightheight(root->right); hrl = leftheight(root->right);
                    hl = hll; hll = leftheight(root->left);   hlr = rightheight(root->left);
                }
            }
            return ans;
        }
        int leftheight(TreeNode* root){
            int ans = 0;
            while(root){ root = root->left; ans++; }
            return ans;
        }
        int rightheight(TreeNode* root){
            int ans = 0;
            while(root){ root = root->right; ans++; }
            return ans;
        }
    };
    

Log in to reply
 

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