654. 最大二叉树

题目描述：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

测试用例：

示例 1:

输入：nums = [3,2,1,6,0,5]

输出：[6,3,5,null,2,0,null,null,1]

解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
   - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
       - 空数组，无子节点。
       - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
           - 空数组，无子节点。
           - 只有一个元素，所以子节点是一个值为 1 的节点。
   - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
       - 只有一个元素，所以子节点是一个值为 0 的节点。
       - 空数组，无子节点。

示例2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

限制及提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

---

解题分析及思路：

本题解法有分治法、单调栈 🔗等，感兴趣的可以自己去实现。这里展示hash + 排序 、分治两种方法

方法一：hash + 排序

首先要构造根节点，然后根据根节点依次构建其左右节点。

• 根节点所在位置的左边中最大值为其左节点
• 根节点所在位置的右边中最大值为其右节点

那么，如何知道根节点以及其左右节点呢。

只需对元素组进行排序即可。

那么，如何知道排序后的值所对应的下标与根节点的位置关系呢？

只需在排序前将其树值与下标作为map存储即可。

func constructMaximumBinaryTree(nums []int) *TreeNode {
	l := len(nums)
	m := make(map[int]int)
	for i := 0; i < l; i++ {
		m[nums[i]] = i
	}
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] >= nums[j]
	})
	root := &TreeNode{
		Val: nums[0],
	}
	var insertNode func(node *TreeNode, num int)
	insertNode = func(node *TreeNode, num int) {
		if m[node.Val] > m[num] {
			if node.Left == nil {
				node.Left = &TreeNode{
					Val: num,
				}
			} else {
				insertNode(node.Left, num)
			}
		} else {
			if node.Right == nil {
				node.Right = &TreeNode{
					Val: num,
				}
			} else {
				insertNode(node.Right, num)
			}
		}
	}
	for i := 1; i < l; i++ {
		insertNode(root, nums[i])
	}
	return root
}

复杂度：

• 时间复杂度：O(n * logN)
• 空间复杂度：O(n)

执行结果：

• 执行用时：40 ms, 在所有 Go 提交中击败了6.08%的用户
• 内存消耗：6.9 MB, 在所有 Go 提交中击败了95.77%的用户

方法二：分治法

分：根据当前数组中最大值将其分割为左右两个数组

治：找到数组当中的最大值，并将其值构建一个节点，并返回

合：将分割的两个组数，找到当前节点的左右节点，构造完整的节点

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    best := 0
    for i, num := range nums {
        if num > nums[best] {
            best = i
        }
    }
    return &TreeNode{nums[best], constructMaximumBinaryTree(nums[:best]), constructMaximumBinaryTree(nums[best+1:])}
}

复杂度：

• 时间复杂度：O(n * logN)
• 空间复杂度：O(n)

执行结果：

• 执行用时：12 ms, 在所有 Go 提交中击败了93.92%的用户
• 内存消耗：6.9 MB, 在所有 Go 提交中击败了95.77%的用户