LeetCode(104) -- 173, 179

P173. Binary Search Tree Iterator (Medium)

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

My Solution

class BSTIterator {

    List<Integer> list = new ArrayList<>();
    Iterator<Integer> iterator;
    
    public BSTIterator(TreeNode root) {
        inOrder(root);
        iterator = list.iterator();
    }

    /** @return the next smallest number */
    public int next() {
        return iterator.next();
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return iterator.hasNext();
    }
    
    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }       
        inOrder(node.left);
        list.add(node.val);
        inOrder(node.right);
    }
}

49%

The Best Solution

class BSTIterator {

    TreeNode root;

    public BSTIterator(TreeNode root) {
        this.root = root;
    }

    public int next() {
        TreeNode node = root;
        TreeNode parent = null;
        if (node.left == null) {
            root = root.right;
            return node.val;
        }

        while (node.left != null) {
            parent = node;
            node = node.left;
        }

        if (node.right != null) {
            parent.left = node.right;
        } else {
            parent.left = null;
        }
        return node.val;
    }

    public boolean hasNext() {
        return root != null;
    }
}

P179. Largest Number (Medium)

Given a list of non negative integers, arrange them such that they form the largest number.

Solution

class Solution {
    private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {
            String order1 = o1 + o2;
            String order2 = o2 + o1;
            return order2.compareTo(order1);
        }
    }
    
    public String largestNumber(int[] nums) {
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            asStrs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(asStrs, new LargerNumberComparator());
        if (asStrs[0].equals("0")) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (String asStr : asStrs) {
            sb.append(asStr);
        }
        return sb.toString();
    }
}