二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如,

给定二叉搜索树:

    4/ \2   7/ \
1   3

和 插入的值: 5
你可以返回这个二叉搜索树:

     4/   \2     7/ \   /
1   3 5

或者这个树也是有效的:

     5/   \2     7/ \   
1   3\4

解题思路

递归求解
找到适合的叶节点位置，将给节点作为叶节点插入，结合二叉搜索树的搜索，可进行求解。
1.若root==null，则将val作为一个新的树的结点
2.若val<root.val，将新节点插入到左子树中，递归搜索左子树的节点，依次比较
3.若val>root.val，将新节点插入到右子树中，递归搜索右子树的节点依次比较。
4.最后返回root

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @param {number} val* @return {TreeNode}*/
/*
若是root==null，则返回一插入值为节点的树，TreeNode(val)
若val>root.val，则递归搜索插入到右子树
若val<root.val，则递归搜索插入到左子树
返回root
*/
var insertIntoBST = function(root, val) {if(!root){return new TreeNode(val)}if(val < root.val){root.left = insertIntoBST(root.left,val)}if(val > root.val){root.right = insertIntoBST(root.right,val)}return root
};