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.

http://www.lintcode.com/en/problem/max-tree/

Discussion

O(n^2)思路比较简单，递归构建左右子树。会超时。

题目要求O(n) run time，用个stack维护一个递减序列。对于一个新节点：

• 如果比栈顶元素小或者等，直接入栈
• 若比栈顶元素大，则将栈里所有比该新节点小的节点一次弹出，这些弹出的节点构造的子树是新节点的左子树（因为新节点是后来的嘛）。然后将新节点入栈
• 用弹出的节点构造子树的时候后弹出的节点是先弹出的节点的右孩子（因为先弹出的是后来的并且比后弹出的小）
• 遍历完数组里所有元素以后，栈底的元素就是tree 的note（最大的在最栈底嘛），若此时有多个节点在stack里，一次弹出构造子树，同样后弹出的节点是先弹出的节点的右孩子，最后一个弹出的是root。

Solution

思路1：time limited

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 maxTree(A, 0, A.size()-1);
    }
    TreeNode *maxTree(vector<int> A, int start, int end) {
        if(start > end) return NULL;
        int max = INT_MIN;
        int idx = start;
        for(int i=start; i<=end; i++) {
            if(A[i] > max) {
                max = A[i];
                idx = i;
            }
        }
        TreeNode *root = new TreeNode(max);
        root->left = maxTree(A, start, idx-1);
        root->right = maxTree(A, idx+1, end);
        return root;
    }
};

Solution 2: using a stack.

// Time:  O(n)
// Space: O(n)
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
        if(A.size() == 0) return NULL;
        stack<TreeNode*> mystk;
        TreeNode *init = new TreeNode(A[0]);
        mystk.push(init);
        for(int i=1; i<A.size(); i++) {
            TreeNode *cur = new TreeNode(A[i]);//新节点
            if(A[i] <= mystk.top()->val) {比栈顶元素小或者等，直接入栈
                mystk.push(cur);
            } else {
                TreeNode *smaller = mystk.top();
                mystk.pop();
                while(mystk.empty()==false && A[i]> mystk.top()->val) {//
                    TreeNode *tmp = mystk.top();//弹出的节点构造子树
                    mystk.pop();
                    tmp->right = smaller;
                    smaller = tmp;
                }
                cur->left = smaller;//这些弹出的节点构造的子树是新节点的左子树
                mystk.push(cur);
            }
        }
        TreeNode *root = mystk.top();//弹出的节点是先弹出的节点的右孩子，最后一个弹出的是root
        mystk.pop();
        while(mystk.empty() == false) {
            TreeNode *tmp = mystk.top();
            mystk.pop();
            tmp->right = root;
            root = tmp;
        }
        return root;
    }
};