Can someone tell what goes wrong with my code? Thanks


  • 0
    S
    public class Solution {
        class TreeNode {
            int val;
            int smallerCnt;
            TreeNode left;
            TreeNode right;
            
            public TreeNode(int val, int smallerCnt) {
                this.val = val;
                this.smallerCnt = smallerCnt;
                left = null;
                right = null;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            Integer[] res = new Integer[nums.length];
            TreeNode root = null;
            for (int i = nums.length - 1; i >= 0; i--) {
                res[i] = insert(root, nums[i]);
            }
    
            return Arrays.asList(res);
        }
        // return the number of elements less than the inserted value
        private int insert(TreeNode root, int v) {
            if (root == null) {
                root = new TreeNode(v, 0);
                return root.smallerCnt;
            }
            if (root.val > v) {
                root.smallerCnt++;
                return insert(root.left, v);
            }
            else {
                return insert(root.right, v) + root.smallerCnt + (root.val < v ? 1 : 0);
            } 
        }
    }
    
    

  • 0
    W

    You didn't handle the case of same values.


Log in to reply
 

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