C++ iteratively solution in 53ms


  • 0
    G

    Using dichotomy to calculate the final node whose left and right are not in equal height, h1 can get by the last calculation

    /**
     * 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 getHeight(TreeNode* root){
            int h = 0;
            while(root){ h++; root = root->left;}
            return h;
        }
        
        int countNodes(TreeNode* root) {
            TreeNode* head = root ;
            int h1 = -1, h2 =0,  head_num =1;
            while(head){
                if (h1 == -1) h1=getHeight(head->left);
                h2=getHeight(head->right);
    
                if (h1 == 1 && h2==0) return head_num*2;
                if (h1 == 0 && h2==0) return head_num;
                if (h1 == 1 && h2==1) return head_num*2+1;
                
                if (h1 > h2){
                    head_num = head_num*2;
                    head = head->left;
                    h1--;
                }else{
                    head_num = head_num*2+1;
                    head = head->right;
                    h1 = h2 -1;
                }
            }
            return 0;
            
            
        }
    };
    

Log in to reply
 

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