Max Tree

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.
还是用到了ordered stack。对于每个数，他的左右右节点是在他与第一个比他大的数之间，比他小的最大数，因此维护一个递减stack就可以得到。

----------------------- thinking----------------------------
https://codesolutiony.wordpress.com/2015/01/28/lintcode-max-tree/
---------------------- codes ----------------------------------
/**
 * 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
        stack<TreeNode*> stack;
        for (int i = 0; i < A.size(); i++) {
            TreeNode * pre = NULL;
            TreeNode * ele = new TreeNode(A[i]);
            while (!stack.empty() && stack.top()->val < A[i]) {
                TreeNode *cur = stack.top();
                stack.pop();
                cur->right = pre;
                pre = cur;
                ele->left = cur;
            }
            stack.push(ele);
        }
        TreeNode * pre = NULL;
        while (!stack.empty()) {
            TreeNode * cur = stack.top();
            stack.pop();
            cur->right = pre;
            pre = cur;
        }
        return pre;
    }
};