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

Solution:

本质上是个递减栈的操作，解题思路确认我的父亲是谁，

[2, 5, 6, 0, 3, 1] 的递减栈是： [6 3 1], 栈里存储的是树节点，第一个节点即是问题的答案。

(1) Create the Node with val = 2 and push it into stack

(2) create the Node(5) and compare 5 > 2 which means it's not a decreasing stack, so need to pop 2 first and make current node(5).left = pop(2) and if stack is not empty means there are a parent for node(5) and need to do stack.peek().right = node(5)

(3) the last step is push the node into stack

(4) in the last step the decreasing stack looks like [6, 3 ,1]

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
        stack = []
        for item in A:
            node = TreeNode(item)
            # item is greater than the existing like 2 or 3 items then put them as it's left child
            while stack and item >= stack[-1].val:
                node.left = stack.pop()
            if stack :
                stack[-1].right = node
            stack.append(node)
        return stack[0]