654. Maximum Binary Tree

1.問題

• 給予一個不重複的整數陣列, build一個maximum tree:

  • root是陣列中的最大值

  • 左子樹是左邊區間

  • 右子樹是右邊區間

2.想法

• Recursion

  • 找出區間的最大值並作為下一層的root

3.程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode *root = new TreeNode(0);
        getNode(root, nums, 0, nums.size() - 1);
        return root;
    }
private:
    void getNode(TreeNode *root, vector<int>& nums, int low, int high)
    {
        if (low > high)
        {
            root = NULL;
            return;
        }
        else if (low == high)
        {
            root->val = nums[high];
            return;
        }
        int maxNum = nums[low];
        int res = low;
        for (int i = low; i <= high; i++)
        {
            if (nums[i] > maxNum)
            {
                maxNum = nums[i];
                res = i;
            }
        }
        root->val = nums[res];
        
        if (low <= res - 1)
        {
            getNode(root->left = new TreeNode(0), nums, low, res - 1);   
        }
        if (res + 1 <= high)
        {
            getNode(root->right = new TreeNode(0), nums, res + 1, high);
        }
    }
};

4.Performance