1/17, modified BST

如果没说，一定要make sure是不是BST，是的话通常要利用BST的性质。

• 左子树中所有节点小于root，右子树中所有节点大于root。
• 最左边的节点是BST的最小值，最右边的是最大值。
• 对BST的inorder traversal会得到一个sorted结果。

Count of Smaller Numbers After Self

note: preSum is the count before root.parent. It would be changed only when going right. root.segmentLeftCount is the count between root.parent and root. It would be changed only when going left. at this time, root.parent <= num < root, so increase root.segmentLeftCount.

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if(nums == null || nums.length == 0) return new ArrayList<>();

        TreeNode root = null;
        Integer[] res = new Integer[nums.length];
        for(int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, res, i, 0);
        }
        return Arrays.asList(res);
    }

    private TreeNode insert(int num, TreeNode root, Integer[] res, int index, int preSum) {
        if(root == null) {
            // create new node no matter if it is duplicated
            res[index] = preSum;
            root = new TreeNode(num);
        } else if(num >= root.val) {
            // only change the preSum when going right,
            // 1) preSum is the count before root.parent
            // 2) root.segmentLeftCount is the count between root.parent and root
            // 3) num > root.val ? 1 : 0 is the count of root itself,
            // if the statement of question is "smaller or equals to", it will be always 1
            root.right = insert(num, root.right, res, index, preSum + root.segmentLeftCount + (num > root.val ? 1 : 0));
        } else {
            // only change segmentLeftCount when going left
            // at this time, root.parent <= num < root, so increase root.segmentLeftCount
            root.segmentLeftCount++;
            root.left = insert(num, root.left, res, index, preSum);
        }
        return root;
    }

    class TreeNode {
        public int val, segmentLeftCount = 0;
        TreeNode left = null, right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public String toString() {
            return val + "(" + segmentLeftCount + ")";
        }
    }
}