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 is

              6

            /    
         5       3

       /        /   
     2        0     1

 

 

Challenge
O(n) time complexity

Analysis:

Recursion: use recursion method, in the worst case, the complexity is O(n^2).

public TreeNode maxTree(int[] A) {    
        // 2015-09-05  
        if (A == null || A.length == 0) {  
            return null;  
        }  
        // 栈中点的值递减  
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();    
    
        // 循环len + 1次    
        for (int i = 0; i <= A.length; i++) {    
            // 假设在数组的最后加上第n+1个数，大小为正无穷    
            TreeNode curNode = (i == A.length) ? new TreeNode(Integer.MAX_VALUE)  : new TreeNode(A[i]);    
              
            // 一次循环pop一次  
            while (!stack.isEmpty() && curNode.val > stack.peek().val) {    
                TreeNode popNode = stack.pop();   
                // 下面分析将popNode放在哪  
                if (stack.isEmpty()) {    
                    curNode.left = popNode;    
                } else {    
                    TreeNode leftPop = stack.peek();    
                    if (leftPop.val > curNode.val) {    
                        curNode.left = popNode;    
                    } else {    
                        leftPop.right = popNode;    
                    }    
                }    
            } // while  
            stack.push(curNode);    
        }    
        // 最后push进去的是第n + 1个点    
        return stack.peek().left;    
}