binary search. java. 44ms. 99% beat


  • 0
    Y

    The key idea is to find the mid node of current tree x: which is
    x.right.left.left...left until null. Then use this mid to guide which subtree of x to go.
    Search until reach the bottom leaf.
    And during the searching process, we need to track the position of current tree's root in its level.

        private int binarySearch(TreeNode root) {
            /*
            while the current tree is not leaf:
                int comp = mid is null ?
                if true:  root = root.left,  p = p*2
                    else: root = root.right, p = p*2 + 1.       p: position 
            */
            // first get the Height of the tree.
            int H = 0;
            TreeNode x = root;
            while (null != x) {
                ++H;
                x = x.left;
            }
    
            // search for the last node in bottom level.
            int p = 0;
            int level = 0;
            x = root;
            while (null != x &&  !(x.left == null && x.right == null)) {
                // mid.
                TreeNode mid = x.right;
                int searchDepth = level + 1;
                while (null != mid) {
                    mid = mid.left;
                    ++searchDepth;
                }
    
                if (searchDepth < H) {  // mid: null: go left tree.
                    x = x.left;
                    p <<= 1;                // p = 2*p  + 0;
                    ++level;
                }
                else {
                    x = x.right;
                    p = (p << 1) + 1;       // p = 2*p  + 1;
                    ++level;
                }
            }
            //  nodes: the complete internal tree:   1 << (H - 1)   - 1.   
            //  nodes: bottom level:   1 + p 
            return p + (1<<(H - 1));
        }
    
    

Log in to reply
 

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