> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/601-800/654.-zui-da-er-cha-shu.md).

# 654. 最大二叉树

<https://leetcode-cn.com/problems/maximum-binary-tree/>

## 解法一：递归

用一个辅助函数

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self.helper(nums, 0, len(nums)-1)    #辅助函数
    
    def helper(self, nums, left, right):
        if left > right:    #递归出口
            return None
        i = nums.index(max(nums[left:right+1]))    #找最大值下标
        root = TreeNode(nums[i])
        root.left = self.helper(nums, left, i-1)
        root.right = self.helper(nums, i+1, right)
        return root
```

也可以不用辅助函数

```python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:    #递归出口
            return None
        i = nums.index(max(nums))    #找最大值下标
        root = TreeNode(nums[i])
        root.left = self.constructMaximumBinaryTree(nums[:i])
        root.right = self.constructMaximumBinaryTree(nums[i+1:])
        return root
```

## 解法二：c++

用map,一次遍历加map插入,复杂度O(n\*logn),比较难理解. 关键在于map是有序的,每次插入后都会按key值重新排序,这样就理解为何要与begin,end比较.

另一个关键是为何处理完左子树后要把左边部分清除,因为是按从左到右的顺序读取nums的,因此当读取到nums\[i]时,其左侧的元素都已确定并处理,若不清除的话,再读入nums\[i]右侧的元素,插入map后就丢失元素位置信息了(map会重新排序,切记!),因此把左侧删掉后,map中剩下的就全是右侧元素了.

最后返回rbegin,即倒数第一个元素,map中key最大的值肯定是root,为何这样用呢?也很简单,因为end是不存储信息的,所以不能返回end

```cpp
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    map<int, TreeNode*> q = { { nums[0], new TreeNode(nums[0]) } };
    // 遍历nums,插入map
    for (auto i = 1; i < nums.size(); ++i) {
        auto it_b = q.insert({ nums[i], new TreeNode(nums[i]) }); 
        if (it_b.first != q.begin()) { // 若插入的元素在map中不是第一个,插入left tree.
            it_b.first->second->left = next(it_b.first, -1)->second;
            q.erase(q.begin(), it_b.first); // 将左边部分清除
        }
        if (next(it_b.first, 1) != q.end()) // 若插入的元素的下一个不是end,则将其下一个插入right tree.
            next(it_b.first, 1)->second->right = it_b.first->second;
    }
    return q.rbegin()->second; //返回map中最后一个(不是end)
}
```