题目

leetcode701:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree

代码与解析

说实话，这道题刚看到，想到一个很蠢的办法：遍历二叉搜索树，然后将值存入数组，然后将盖val插入数组，后排序，或者直接中序遍历，然后将值插入数组，然后根据该数组生成二叉搜索树。

实际上这道题可以更简单，可以用递归法
递归三部曲：

• 确定参数及返回值，
  要传入根节点指针，要插入元素，返回新插入节点指针

• 确定终止条件
  如果遇到空节点，说明这里就是要插的位置，
  具体原因可以参考一下carl大佬的博客：：点我：：
  这里讲解的很好，有很多种插入的方式，
  这里贴一下go语言实现：

if root==nil{
    root = &TreeNode{Val:val}
    return root
}

• 确定单层逻辑
  根据值判断当前要插入值在遍历的节点的位置的哪个位置，

if root.Val > val {
    root.Left = insertIntoBST(root.Left, val)
} else {
    root.Right = insertIntoBST(root.Right, val)
}

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}