题目链接：LeetCode 654. 最大二叉树
题意：
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为 nums 中的最大值。
- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
解题思路：
递归法
直接按题目描述进行模拟即可。
用递归函数 constructMaximumBinaryTree(nums []int) 表示对于 对于数组nums构建满足题目要求的最大二叉树，
在单层的递归逻辑中，找出当前数组中的最大值，然后最大值左边的数构建左子树，最大值右边的数构建右子树。
递归代码如下：
//需要考虑的问题：1. 如何找到最大值？ 2. 找到最大值之后要标记最大值的位置
func constructMaximumBinaryTree(nums []int) *TreeNode {
var root TreeNode
if len(nums) == 0{ //递归退出条件
return &root
}
//递归中的处理逻辑
max := nums[0]
index :=0
for k,v:=range nums{// 遍历数组，找到此时nums数组中的最大值以及下标
if v > max{
max = v
index = k
}
}
root.Val = max
if index > 0 { //最大值左边的数成为左子树
root.Left = constructMaximumBinaryTree(nums[:index])
}
if index < len(nums)-1 { //最大值右边的数成为右子树
root.Right = constructMaximumBinaryTree(nums[index+1:])
}
return &root
}
笛卡尔树
其实本题的本质上是通过nums数组构建一个笛卡尔树，因此这里介绍一下笛卡尔树的相关知识。
定义
笛卡尔树是一种二叉树，每一个结点由一个键值二元组 (k,w) 构成。
要求 k 满足二叉搜索树的性质（中序遍历是原序列），而 w 满足堆的性质（左右子树的值大于(/小于)根节点的值）。
如果笛卡尔树的 k,w 键值确定，k,w 互不相同，那么这个笛卡尔树的结构是唯一的。
上面这棵笛卡尔树相当于把数组元素值当作键值 w ,把数组下标当作键值 k .
显然可以发现：这棵树的键值 k 满足二叉搜索树的性质，而键值 w 满足小根堆的性质。
其实这是一种特殊的笛卡尔树，键值 k 正好对应数组下标。更一般的情况则是任意二元组构建的笛卡尔树。
栈构建
将元素按键值 k 排序（也就是下标），先后插入当前的笛卡尔树中，那么我们每次插入的元素必然在这个树的右链(从根节点一直往右子树走形成的链) 的末端。
执行这样一个过程：
从下往上比较右链节点与当前加入节点 x 的键值 w：
-
如果找到右链上的节点 u 满足 w[u] < w[x] ，那么把 x 接到 u 的右儿子上，而以 u 为根的右子树变成了 x 的左子树，然后停止加入过程。
-
如果没有找到右链上的节点，那么 x 就是新根，把原来的树当成 x 的左儿子。
每次添加值都需要进行一次这样的比较。
构建过程示意图如下图所示：
显然，每个数最多进出右链一次，这个过程可以用栈进行维护，栈中维护当前笛卡尔树右链上的节点，不在右链就弹出，时间复杂度为 O(n)
笛卡尔树代码：
func constructMaximumBinaryTree(nums []int) *TreeNode {
// 维护一个栈，将右子树存到栈中，
var st []*TreeNode
for _,v:=range nums{ //依次从前向后遍历数组
node := TreeNode{v,nil,nil} //声明当前的节点
//如果栈不空，并且栈顶元素的值小于当前元素的值，则进行下面循环，直到栈顶元素的值 不小于 当前元素的值
for (len(st) > 0 && st[len(st)-1].Val < node.Val){
node.Left = st[len(st)-1] //则将栈顶元素变成当前节点的左子树
st = st[:len(st)-1] //栈顶元素出栈
}
if (len(st) > 0){
st[len(st)-1].Right = &node //当栈顶元素不在小于当前元素时，则将当前节点变成栈顶元素的右子树
}
st = append(st,&node) //当前元素入栈
}
//循环结束后，如果栈里面的元素 > 1，则将剩余的都弹出，只保留栈底，因为栈底是整个树的根
for len(st) >1 {
st = st[:len(st)-1]
}
return st[0]
}