将有序数组转换为二叉搜索树
LeetCode108. 将有序数组转换为二叉搜索树
给你一个整数数组nums，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
思路
如果根据数组构造一棵二叉树。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
有序数组构造二叉搜索树，寻找分割点比较容易，分割点就是数组中间位置的节点。
删除/增加二叉树节点，都是用递归函数的返回值来完成，这样是比较方便的。
首先取数组中间元素的位置，取了中间位置，就开始以中间位置的元素构造节点，接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点，最后返回root节点
代码
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 { //终止条件，最后数组为空则可以返回
return nil
}
idx := len(nums) / 2
root := &TreeNode{Val: nums[idx]}
// 左递归 root的左孩子接住下一层左区间的构造节点
root.Left = sortedArrayToBST(nums[:idx])
// 右递归 root的右孩子接住下一层右区间构造的节点
root.Right = sortedArrayToBST(nums[idx+1:])
return root
}
|
Link
GitHub