BST与有序数组转换
一句话说明
有序数组转 BST 就是取中点做根；BST 转数组就用中序遍历还原有序序列。
Go 代码：有序数组转 BST
func sortedArrayToBST(nums []int) *TreeNode {
var build func(left, right int) *TreeNode
build = func(left, right int) *TreeNode {
if left > right {
return nil
}
mid := left + (right-left)/2
root := &TreeNode{Val: nums[mid]}
root.Left = build(left, mid-1)
root.Right = build(mid+1, right)
return root
}
return build(0, len(nums)-1)
}Go 代码：BST 转有序数组
func bstToSortedArray(root *TreeNode) []int {
result := []int{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
result = append(result, node.Val)
inorder(node.Right)
}
inorder(root)
return result
}