# 654. Maximum Binary Tree

## 1.問題

* 給予一個不重複的整數陣列, build一個maximum tree:
  * root是陣列中的最大值
  * 左子樹是左邊區間
  * 右子樹是右邊區間

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LJ3a-wNkNyqYMoUW7wa%2F-LJ3aevHQ5KNAqQKukqV%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-04%20%E4%B8%8B%E5%8D%887.01.57.png?alt=media\&token=a892c2ec-151a-41cb-abfb-07fc68b113b0)



## 2.想法

* Recursion&#x20;
  * 找出區間的最大值並作為下一層的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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LJ3a-wNkNyqYMoUW7wa%2F-LJ3bKL_cZmhWRzeLqVZ%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-04%20%E4%B8%8B%E5%8D%887.02.11.png?alt=media\&token=613ecaa0-f31a-4611-b03a-e5df6a4f786a)
