Java BST solution


  • 0
    S
        class TreeNode {
            TreeNode left,right;
            int val, leftCount, eqCount;
            
            public TreeNode (int val) {
                this.val = val;
                this.leftCount = 0;
                this.eqCount = 0;
                
            }
        }
        
        public List<Integer> countSmaller(int[] nums) {
            int n = nums.length, i;
            List<Integer> result = new ArrayList<>(n);
            if (n == 0)
                return result;
                
            TreeNode root = new TreeNode(nums[n-1]);
            root.eqCount++;
            result.add(0);
            for (i=n-2;i>=0;i--) {
                result.add(insertNode(root, nums[i]));
            }
            Collections.reverse(result);
            return result;
        }
        
        public int insertNode (TreeNode root, int num) {
            int leftCount = 0;
            if (root.val > num) {
                root.leftCount++;
                if (root.left == null)
                    root.left = new TreeNode(num);
                leftCount = insertNode(root.left, num);
            } else if (root.val < num) {
                leftCount = root.leftCount + root.eqCount;
                if (root.right == null)
                    root.right = new TreeNode(num);
                leftCount += insertNode(root.right, num);
            } else {
                leftCount = root.leftCount;
                root.eqCount++;
            }
            return leftCount;
        }
    }

Log in to reply
 

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