654. 最大二叉树

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

解法一：递归

用一个辅助函数

# 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

也可以不用辅助函数

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

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)
}