A Binary search mathod


  • 0
    L

    We use binary search on the last layer, the commentsin code shows details.

    /**
     * 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 {
    private:
        bool leaf_is_null(TreeNode *r, int depth, int begin, int index)
        {
            // check whether the leaf is null
            auto *ptr = r;
            for(int i=depth-begin-1;i>=0;--i)
            {
                bool take_right = (index>>i) & 1;
                if(take_right) ptr = ptr->right;
                else ptr = ptr->left;
            }
            return ptr==nullptr;
        }
    public:
        int countNodes(TreeNode* root) {
            if(root==nullptr) return 0;
            int r_level = 0, l_level = 0;
            auto *ptr = root;
            
            // first we get the depth of the tree 
            while(ptr!=nullptr)
            {
                ++r_level;
                ptr = ptr->right;
            }
            ptr = root;
            while(ptr!=nullptr)
            {
                ++l_level;
                ptr = ptr->left;
            }
            
            if(l_level==r_level) return (1<<r_level) - 1;
            
            // We know that the last node of the tree is in the d-th layer 
            // and is between the 0th and 2^(d-1)-1th node of the last layer,
            // we can use binary search on the last layer.
            // Using binary form of the index of nodes in the last layer,
            // we can see that each 1 in the binary form now becomes
            // an operation that we choose the right child,
            // and each 0 represents the left child.
            // Here we try to find the first null leaf in the last layer.
            int l_bd = 0, r_bd = (1<<(l_level-1))-1, curr_level = 1;
            ptr = root;
            while(r_bd > l_bd)
            {
                int mid = max((l_bd + r_bd)>>1, 0);
                if(leaf_is_null(ptr, l_level, curr_level, mid))
                {
                    ptr = ptr->left;
                    r_bd = mid;
                }
                else
                {
                    ptr = ptr->right;
                    l_bd = mid+1;
                }
                ++curr_level;
            }
            
            return (1<<r_level) - 1 + l_bd;
        }
    };
    

Log in to reply
 

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