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.

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

这是lintcode上的一题，每次先确定根结点最大值，然后根据根结点再分割左右两边，然后继续。按照描述是一个递归过程。但是直接用递归是O(nlogn)的平均复杂度，最坏复杂度为O(n^2),即为有序数组时，但是这题用递归解法在Lintcode上直接爆栈。

所以需要时间和空间复杂度都为O(n)的解法，仔细分析下这题，给出的数组实际是max-tree的一个中序遍历。max-tree有一个特点，每个节点的祖先节点都比其值大．并且一个父亲节点的两个孩子节点在中序遍历中无法紧邻（必须经过父亲节点）所以一个节点左边和右边第一个比它大的都是它的祖先节点．左右比它小的实际是它的孩子子树遍历的结果．

每个结点的父结点都比结点值要大，并且结合中序遍历的性质，如果结点为父结点的左孩子，则在数组中是［结点...父结点］这样的顺序，而如果是右结点，则在数组中是［父结点...结点]这样的顺序。而省略号代表的是结点自己的右子树序列（结点为父结点的左孩子的情况），结点自己的左子树序列（结点为父结点的左孩子的情况），所以...的内容中都是比结点值小的。所以结点的父结点是其左边或者右边第一个比它大的值。在结点是父结点的左右孩子的情况下，如何确定父亲结点是哪个呢。按照推理我们选择其中比较小的那个。因为左右第一个比它大的值都是它的祖先节点．如果我们选择比较大的那个．则另外一个比较小的节点也是这个节点的祖先节点，爷爷节点及以上，所以这个比较小的节点最终成了这个比较大的节点的祖先节点．显然不符合max-tree的特性．

以上得出结论：每个节点的父亲节点，是其左边和右边第一个比它大的数的中的比较小的那个．显然数据结构是使用单调递减栈，时间和空间复杂度都是O(n),代码如下：

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    # @param A: Given an integer array with no duplicates.
    # @return: The root of max tree.
    def maxTree(self, A):
        # write your code here
        if not A:
            return None
        stack = []
        for i in xrange(len(A)+1):
            right = TreeNode(A[i]) if i < len(A) else TreeNode(sys.maxint)
            while stack and right.val > stack[-1].val:
                nowNode = stack.pop()
                if not stack:
                    right.left = nowNode
                else:
                    left = stack[-1]
                    if left.val > right.val:
                        right.left = nowNode
                    else:
                        left.right = nowNode
                        
            stack.append(right)
        return stack[-1].left

注意最后出栈的值是数组中的最大值，所以为树的根节点，但是最后栈内还有一个值，即sys.maxint生成的节点，该节点的左孩子就是max-tree的根节点．

用了单调栈的性质，但是存的不是数值
步骤：
loop num in A:
1 制作当前current_node = TreeNode(num)
2 loop 如果栈不为空且当前值比peek 大:
那么将peek 置为当前node的左子树
3 如果栈还不为空，那么说明现在peek 比当前值大，就将当前node 置为peek 的右子树
4 把当前node 入栈