[leetcode]Count of Smaller Numbers After Self

用BST加count就可以解决

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        BinarySearchTree tree = new BinarySearchTree();
        for(int i = nums.length-1; i >= 0; i--){
            result.addFirst(tree.add(nums[i]));
        }
        return result;
    }
}

class BinarySearchTree{
    BSTNode root;
    int add(int value){
        BSTNode visit = root;
        int count = 0;
        if (root == null) root = new BSTNode(value);

        while (visit != null){
            if (visit.value == value){
                visit.dupCount++;
                count += visit.leftCount;
                break;
            }else if (visit.value < value){
                count += (visit.dupCount+visit.leftCount);
                if (visit.right == null){
                    visit.right = new BSTNode(value);
                    break;
                }
                visit = visit.right;
            }else{
                visit.leftCount++;  
                if (visit.left == null){
                    visit.left = new BSTNode(value);
                    break;
                }
                visit = visit.left;
            }
        }
        return count;
    }
}

class BSTNode{
    int dupCount = 1;
    int leftCount;
    int value;
    BSTNode left, right;
    BSTNode(int value){
        this.value = value;
    }
}