Share my AC BST solution


  • 5
    S

    Store extra info leftSize and selfSize in the treeNode.
    And add the nodes to the tree using the reverse order of the array
    So, all the numbers after it self will be store in the tree before it.
    Remember using the selfSize to deal with duplicates.

    public class Node {
            Node left;
            Node right;
            int val;
            int leftSize;
            int selfSize;
            public Node(int val) {
                this.val = val;
                selfSize = 1;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> list = new LinkedList<>();
            int n = nums.length;
            if (n == 0) {
                return list;
            }
            Node root = new Node(nums[n - 1]);
            list.add(0);
            for (int i = n - 2; i >= 0; i--) {
                list.add(0, addToTree(root, nums[i])); // add to the front of list
            }
            return list;
        }
        
        private int addToTree(Node root, int val) {
            int num = 0; // store the count less than it
            Node current = root;
            while (true) {
                if (current.val < val) {
                    num += current.leftSize + current.selfSize;
                    if (current.right == null) {
                        current.right = new Node(val);
                        break;
                    }
                    current = current.right;
                } else if (current.val > val) {
                    current.leftSize++; // remember to update the path nodes info
                    if (current.left == null) {
                        current.left = new Node(val);
                        break;
                    }
                    current = current.left;
                } else {
                    current.selfSize++; // duplicates
                    num += current.leftSize;
                    break;
                }
            }
            return num;
        }

  • 0
    L

    In the worst case, the tree needs to be balanced to avoid quadratic runtime, though it is not covered by the test cases.


  • 0
    K

    Yes, so AVL is a better choice.


Log in to reply
 

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