Max Tree

Max Tree

27%

Accepted

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.

Have you met this question in a real interview? 

Yes

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.

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

        Stack<TreeNode> stack = new Stack<TreeNode>();

        

        for(int i = 0; i < A.length; i++){

            TreeNode newNode = new TreeNode(A[i]);

            TreeNode pre = null;

            while(!stack.isEmpty() && stack.peek().val < A[i]){

                TreeNode node = stack.pop();

                if(pre != null){

                    node.right = pre;

                }

                pre = node;

                newNode.left = pre;

            }

            stack.push(newNode);

        }

        

        TreeNode pre = null;

        while(!stack.isEmpty()){

            TreeNode node = stack.pop();

            node.right = pre;

            pre = node;

        }

        return pre;

    }

}