Description

Given an integer array with no duplicates. A max tree building on this array is defined as follow: 1) The root is the maximum number in the array 2) 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 is

                                     6
                                   /   \
                                 5      3
                                /      /  \ 
                               2      0    1

Solution

用一个递减的单调栈来解决。加入一个新node的时候，把前面所有比当前node值小的点pop出来，那么剩下的那个最上面的点就是当先node左边值最大的点，应当为当前node的left节点。pop出来的时候，先pop出来的点是后pop出来的点右边还没插进树里的最大点，即它的右节点。
最后为了pop出stack里面所有剩下的点，放一个值为max value的node进去，最后返回这个node的左支即可。

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.length==0) return null; 

        Stack<TreeNode> nodeStack = new Stack<TreeNode>(); 
        for (int i = 0; i <= len; i++) {
        cur = new TreeNode(i < len ? A[i] : Integer.MAX_VALUE);
        if (stack.isEmpty()) {
            stack.push(cur);
        } else {
            TreeNode node = null;
            TreeNode next = null;
            while (!stack.isEmpty() && cur.val > stack.peek().val) {
                next = stack.pop();
                next.right = node;
                node = next;
            }

            cur.left = node;
            stack.push(left);
        }

        return stack.pop().left;
    } 
}