Max Tree (Ladder)

Description

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * 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> nums) {
        // write your code here
        if (nums.empty()) {
            return nullptr;
        }
        int len = nums.size();
        vector<TreeNode*> stk;
        for (int i = 0; i < len; ++i) {
            TreeNode* cur = new TreeNode(nums[i]);
            // before cur, put any small element in the cur->left
            // the array is divided by cur
            while (!stk.empty() && nums[i] > stk.back()->val) {
                cur->left = stk.back();
                stk.pop_back();
            }
            // if cur is not the largest, put cur as the stk.back()->right
            // the array is divided by stk.back();
            if (!stk.empty()) {
                stk.back()->right = cur;
            }
            stk.push_back(cur);
        }
        // stk[0] keep the max val of the array, or the root of tree
        return stk[0];
    }
   };
   // private:
   //     void siftdown(vector<int>& nums, int k) {
   //         int len = nums.size();
   //         while (k < len) {
   //             int most = k;
   //             if (k * 2 + 1 < len && nums[k*2+1] > nums[k]) {
   //                 most = k * 2 + 1;
   //             }
   //             if (k * 2 + 2 < len && nums[k*2+2] > nums[k]) {
   //                 most = k * 2 + 2;
   //             }
   //             if (k == most) {
   //                 break;
   //             }
   //             swap(nums[most], nums[k]);
   //             k = most;
   //         }
   //         return;
   //     }
   //     TreeNode* createTree(vector<int>& nums, int start) {
   //         int len = nums.size();
   //         if (start > len - 1) {
   //             return nullptr;
   //         }
   //         TreeNode* cur = new TreeNode(nums[start]);
   //         cur->left = createTree(nums, start * 2 + 1);
   //         cur->right = createTree(nums, start * 2 + 2);
   //         return cur;
   //     }
   // };
   

Similar problems

x

Tags

x