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.

/**

* Definition of TreeNode:

* class TreeNode {

* public:

* int val;

* TreeNode *left, *right;

* TreeNode(int val) {

* this->val = val;

* this->left = this->right = NULL;

* }

* }

*/

class Solution {

public:

/\*\*

 \* @param A: Given an integer array with no duplicates.

 \* @return: The root of max tree.

 \*/

TreeNode\* maxTree\(vector<int> A\) {

    // write your code here

    return buildTree\(A, 0, A.size\(\) - 1\);

}



TreeNode\* buildTree\(vector<int>& A, int left, int right\) {

    if \(left > right\) {

        return NULL;

    }

    int index  = left;

    for \(int i = left; i <= right; ++i\) {

        if \(A\[i\] > A\[index\]\) {

            index = i;

        }

    }

    TreeNode\* root = new TreeNode\(A\[index\]\);

    root->left = buildTree\(A, left, index - 1\);

    root->right = buildTree\(A, index + 1, right\);

    return root;

}

};