BST插入
一句话说明
BST 插入就是先找到空位，再把新节点挂上去。
（附件 binary-search.gif 未随站点发布）
Go 代码：递归
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if val < root.Val {
root.Left = insertIntoBST(root.Left, val)
} else if val > root.Val {
root.Right = insertIntoBST(root.Right, val)
}
return root
}Go 代码：迭代
func insertIntoBSTIterative(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
cur := root
for {
if val < cur.Val {
if cur.Left == nil {
cur.Left = &TreeNode{Val: val}
break
}
cur = cur.Left
continue
}
if val > cur.Val {
if cur.Right == nil {
cur.Right = &TreeNode{Val: val}
break
}
cur = cur.Right
continue
}
break
}
return root
}易错点
递归版一定要把返回值接回父节点
空树插入时，新节点本身就是根。