###### tags: `Leetcode` `medium` `tree` `array` `divide and conquer` `python` `c++`

# 654. Maximum Binary Tree

## [題目連結:] https://leetcode.com/problems/maximum-binary-tree/description/

## 題目:
You are given an integer array nums with no duplicates. A **maximum binary tree** can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in ```nums```.

Recursively build the left subtree on the **subarray prefix** to the **left** of the maximum value.

Recursively build the right subtree on the **subarray suffix** to the **right** of the maximum value.

Return the **maximum binary tree** built from ```nums```.


## 解題想法:
* 此題為給一數組，求建構出最大二元樹
* 規則為每次選數組中最大值為root
* 分隔出左右部分數組再創建最大二元樹

* Divide and Conquer:
* 遞歸直接上!!
* Step1: 初始判斷nums是否為空
* 空的話直接return None
* Step2:
* 選出最大的值與其位置(題目說每個數字皆獨立)
* Step3:
* 最大的值為root
* root.left=遞歸(nums[:位置])
* root.right=遞歸(nums[位置+1:])
* return root

## Python:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        #step1: root為nums中最大值
        #step2: 左子樹為 root在原nums中左邊部分遞歸構成
        #step3: 右子樹為 root在原nums中右邊部分遞歸構成
        if not nums:
            return None
        maxNum=max(nums) #找最大值
        pos=nums.index(maxNum) #找最大值在nums的位置
        root=TreeNode(maxNum) #建立新TreeNode
        root.left=self.constructMaximumBinaryTree(nums[:pos])
        root.right=self.constructMaximumBinaryTree(nums[pos+1:])
        return root

result=Solution()
nums = [3,2,1,6,0,5]
ans=result.constructMaximumBinaryTree(nums)
ans.printTree()

## C++:
* 注意，c++的vector並沒有像python的list一樣可以直接max求出最大值
* c++中需使用max_element(nums.begin(), nums.end())，且回傳型態為位址，因此需要前面需要加上*指標進行解參考獲取數字
* [可參考說明:] https://shengyu7697.github.io/std-max_element/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty())
            return nullptr;
        int n=nums.size(), pos;
        //max_element: use pointer to dereference
        int maxNum= *max_element(nums.begin(), nums.end());
        for (int i=0; i<n; i++){
            if (nums[i]==maxNum)
                pos=i;
        }
        TreeNode *root= new TreeNode(maxNum);
        vector<int> leftNums= vector<int>(nums.begin(), nums.begin()+pos);
        vector<int> rightNums= vector<int>(nums.begin()+pos+1, nums.end()); 
        root->left = constructMaximumBinaryTree(leftNums);
        root->right= constructMaximumBinaryTree(rightNums);
        return root;
    }
};