Max Tree 126

Question

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

本题其实是构建笛卡树（Cartesian tree， https://en.wikipedia.org/wiki/Cartesian_tree），经典方法是用单调栈（单调递减栈）。我们堆栈里存放的树，只有左子树，没有右子树，且根节点最大。时间复杂度为O(n)。

1. 如果新来一个数，比堆栈顶的树根的数小，则把这个数作为一个单独的节点压入堆栈。

2. 否则，不断从堆栈里弹出树，新弹出的树以旧弹出的树为右子树，连接起来，直到目前堆栈顶的树根的数大于新来的数。然后，弹出的那些数，已经形成了一个新的树，这个树作为新节点的左子树，把这个新树压入堆栈。

这样的堆栈是单调的，越靠近堆栈顶的数越小。最后还要按照（2）的方法，把所有树弹出来，每个旧树作为新树的右子树。

如果用递归的方法建树，时间复杂度会退化到O(n^2)。

代码如下：

Stack O(n)：

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

        Stack<TreeNode> stack = new Stack<TreeNode>();
        for(int i = 0; i <= A.length; i++){
            TreeNode newNode = i == A.length? new TreeNode(Integer.MAX_VALUE) : new TreeNode(A[i]);
            if(!stack.isEmpty() && stack.peek().val < newNode.val){
                TreeNode curt = stack.pop();
                TreeNode root = curt;
                while(!stack.isEmpty() && stack.peek().val < newNode.val){
                    root = stack.pop();
                    root.right = curt;
                    curt = root;
                }
                newNode.left = root;
            }
            stack.push(newNode);
        }

        return stack.peek().left;
    }
}

Recursive O(n^2):

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

    //     return helper(A, 0, A.length - 1);
    // }

    // private TreeNode helper(int[] A, int start, int end){
    //     if(start > end){
    //         return null;
    //     }

    //     if(start == end){
    //         return new TreeNode(A[start]);
    //     }

    //     Stack<Node> stack = new Stack<Node>();
    //     for(int i = start; i <= end; i++){
    //         if(!stack.isEmpty() && stack.peek().val > A[i]){
    //             continue;
    //         }
    //         stack.push(new Node(A[i], i));
    //     }

    //     TreeNode root = new TreeNode(stack.peek().val);

    //     root.left = helper(A, start, stack.peek().index - 1);
    //     root.right = helper(A, stack.peek().index + 1, end);

    //     return root;
    // }
    }
}