JAVA beat 95%


  • 0
    S

    The basic idea is binary search

    public class Solution {
        public int countNodes(TreeNode root) {
            int dleft = checkLeft(root), dright = checkRight(root);
            if(dleft == dright) return (1 << dleft) - 1;
    
            int lo = 0, hi = 1;
            for(int i = 1; i < dleft; i++) hi <<= 1;
            int sum = hi - 1;
            while(root != null) {
                int subleft = checkLeft(root.right);
                if (dleft == subleft + 1) {
                    lo = lo + (hi - lo) / 2 + 1;  
                    root = root.right;
                }
                else {
                    root = root.left;
                    hi = lo + (hi - lo) / 2;
                }
                dleft--;
            }
            return sum + hi;
        }
        private int checkLeft(TreeNode node) {
            int count = 0;
            while(node != null) {
                node = node.left;
                count++;
            } 
            return count;
        }
        private int checkRight(TreeNode node) {
            int count = 0;
            while(node != null) {
                node = node.right;
                count++;
            } 
            return count;
        }
    }
    
    

Log in to reply
 

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