[LintCode] 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.
 
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.
 
단조로운 창고, 원소를 옮겨다니며, 창고에서 이 원소보다 작은 결점을 합치면, 합쳐진 새로운 결점을 현재 결점의 왼쪽에 걸어줍니다.합병할 때 창고의 결점의 값이 점차 줄어들기 때문에 두 번째 결점을 첫 번째 결점의 오른쪽에 직접 걸어 놓는다.또 이 나무는 카테고리(Cartesian tree)라는 학명이 있다.

 1 /**

 2  * Definition of TreeNode:

 3  * class TreeNode {

 4  * public:

 5  *     int val;

 6  *     TreeNode *left, *right;

 7  *     TreeNode(int val) {

 8  *         this->val = val;

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

10  *     }

11  * }

12  */

13 class Solution {

14 public:

15     /**

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

17      * @return: The root of max tree.

18      */

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

20         // write your code here

21         TreeNode *a, *b, *tmp;

22         stack<TreeNode*> stk;

23         int cur_max = INT_MIN;

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

25             if (i < A.size() && A[i] < cur_max) {

26                 tmp = new TreeNode(A[i]);

27                 stk.push(tmp);

28             } else {

29                 b = NULL;

30                 while (!stk.empty() && (i == A.size() || stk.top()->val < A[i])) {

31                     b = stk.top(); stk.pop();

32                     if (!stk.empty()) a = stk.top()->right = b;

33                 }

34                 if (i < A.size()) {

35                     tmp = new TreeNode(A[i]);

36                     tmp->left = b;

37                     stk.push(tmp);  

38                 } else {

39                     stk.push(b);

40                 }

41             }

42         }

43         return stk.top();

44     }

45 };