最大二叉树
一句话说明
最大二叉树就是每次把当前区间的最大值拿来当根，然后继续分治左右两边。
Go 代码
func constructMaximumBinaryTree(nums []int) *TreeNode {
var build func(left, right int) *TreeNode
build = func(left, right int) *TreeNode {
if left > right {
return nil
}
maxIdx := left
for i := left + 1; i <= right; i++ {
if nums[i] > nums[maxIdx] {
maxIdx = i
}
}
root := &TreeNode{Val: nums[maxIdx]}
root.Left = build(left, maxIdx-1)
root.Right = build(maxIdx+1, right)
return root
}
return build(0, len(nums)-1)
}关键点
这题本质上就是分治，和“取中点做根”的思路很像，只不过这里取的是最大值。