Lintcode 126. Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

• The root is the maximum number in the array
• The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

    6
   / \
  5   3
 /   / \
2   0   1

Challenge

O(n) time and memory.

Solution:
For any node x of the array, its parent must be the first number greater than it. 
– ….., L, <X, …,<X, X, <X, …, <X, R,…
– 如果L<R，[L, R]里一定R先做根。然后[L, R)里L先做根，然后就是X
– 如果L>R， [L, R]里一定L先做根。然后(L, R]里R先做根，然后就是X
• 如何找到每个值左右第一个比它大的值？
– 单调递减栈

Code (Java)

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(new TreeNode(A[0]));

        for (int i = 1; i < A.length; i++) {
            TreeNode curr = new TreeNode(A[i]);
            while (!stack.isEmpty() && curr.val > stack.peek().val) {
                TreeNode top = stack.pop();
                if (stack.isEmpty() || curr.val < stack.peek().val)  {
                    curr.left = top;
                } else {
                    stack.peek().right = top;
                }
            }
            stack.push(curr);
        }

        // now the stack is a mono descreasing stack
        //
        while (stack.size() > 1) {
            TreeNode top = stack.pop();
            stack.peek().right = top;
        }

        return stack.pop();
    }
}