LeetCode 0654.最大二叉树

最大二叉树

LeetCode654. 最大二叉树

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

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

返回nums构建的 最大二叉树

思路

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树

确定递归函数的参数和返回值
- 参数：传入存放元素的数组
- 返回值：返回二叉树的根节点
确定终止条件
- 若传入数组的长度小于1，则返回nil
确定单层递归的逻辑
- 先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组
- 然后用最大值所在的下标左区间构造左子树；用最大值所在的下标右区间构造右子树

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


//构造最大二叉树
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) < 1 {
        return nil
    } //若传入数组为空 则直接返回nil
    //首先找到最大值
    index := findMax(nums)
    //然后构造二叉树
    root := &TreeNode{
        Val:   nums[index],
        Left:  constructMaximumBinaryTree(nums[:index]),   //左半边
        Right: constructMaximumBinaryTree(nums[index+1:]), //右半边
    }
    //最后返回根节点
    return root
}

//找到传入数组中的最大值返回下标
func findMax(nums []int) (index int) {
    for i := 0; i < len(nums); i++ {
        if nums[i] > nums[index] {
            index = i
        }
    }
    return
}

Link

GitHub