BST定义
二叉搜索树是二叉树的一种特殊表示形式，它满足如下特性：
- 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
- 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。
?
//定义二叉树节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//定义二叉树
type BinareSearchTree struct {
Root *TreeNode
}
二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果 。
示例：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
?
BST插入的实现
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
p := root
for p != nil {
if val < p.Val {
if p.Left == nil {
p.Left = &TreeNode{Val: val}
break
}
p = p.Left
} else {
if p.Right == nil {
p.Right = &TreeNode{Val: val}
break
}
p = p.Right
}
}
return root
}
数组遍历构造一棵二叉搜索树
实现了BST的插入，现在我们可以构造一棵二叉搜索树了：
//实现了图2左边二叉搜索树的构造
nums := []int{2,7,1,3}
root := &TreeNode{4,nil,nil}//需要先初始化一个根节点
for _, num := range nums {
insertIntoBST(root, num)
}
中序遍历BST
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
递归的方式：
//中序遍历二叉树
func midOrderTraversal(root *TreeNode) (res []int) {
var midOrder func(node *TreeNode)
midOrder = func(node *TreeNode) {
if node == nil{
return
}
midOrder(node.Left)
res = append(res,node.Val)
midOrder(node.Right)
}
midOrder(root)
return
}
除了递归函数，我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。
非递归的方式（使用栈，弹出时打印）
//使用栈实现中序遍历
func midOrderTraversal2(root *TreeNode) (res []int) {
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return
}
验证一棵树是否是二叉搜索树
设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r)(l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。
函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。
//判断是否是二叉搜索树
func isValidBST(root *TreeNode) bool {
return 9helper(root, math.MinInt64, math.MaxInt64)
}
func helper(root *TreeNode, lower, upper int) bool {
if root == nil {
return true
}
if root.Val <= lower || root.Val >= upper {
return false
}
return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}
二叉搜索树迭代器
**题目：**实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器： BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。 boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。 int next()将指针向右移动，然后返回指针处的数字。 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
?
**思路：**根据二叉搜索树的性质，不难发现，原问题等价于对二叉搜索树进行中序遍历。因此，我们可以直接对二叉搜索树做一次完全的递归遍历，获取中序遍历的全部结果并保存在数组中。随后，我们利用得到的数组本身来实现迭代器。
type BSTIterator struct {
arr []int
}
func Constructor(root *TreeNode) (it BSTIterator) {
it.inorder(root)
return
}
func (it *BSTIterator) inorder(node *TreeNode) {
if node == nil {
return
}
it.inorder(node.Left)
it.arr = append(it.arr, node.Val)
it.inorder(node.Right)
}
func (it *BSTIterator) Next() int {
val := it.arr[0]
it.arr = it.arr[1:]
return val
}
func (it *BSTIterator) HasNext() bool {
return len(it.arr) > 0
}
在二叉搜索树中实现删除操作
删除要比我们前面提到过的两种操作复杂许多。有许多不同的删除节点的方法，这篇文章中，我们只讨论一种使整体操作变化最小的方法。我们的方案是用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数，我们需考虑以下三种情况：
- 如果目标节点没有子节点，我们可以直接移除该目标节点。
- 如果目标节只有一个子节点，我们可以用其子节点作为替换。
- 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
我们来看下面这几个例子，以帮助你理解删除操作的中心思想：
?
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return root
}
if key == root.Val {
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
cur := root.Right
for cur.Left != nil {
cur = cur.Left
}
cur.Left = root.Left
root = root.Right
return root
}
if key < root.Val {
root.Left = deleteNode(root.Left, key)
}
if key > root.Val {
root.Right = deleteNode(root.Right, key)
}
return root
}