701-二叉搜索树中的插入操作-medium

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

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

例如,

给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5

你可以返回这个二叉搜索树:

     4<br />       /   \<br />      2     7<br />    / \   /<br />  1   3 5<br />或者这个树也是有效的:
     5<br />       /   \<br />      2     7<br />     / \    <br />   1    3<br />            \<br />               4<br />来源：力扣（LeetCode）<br />链接：[https://leetcode-cn.com/problems/insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree)

思路：
利用二叉搜索树的性质， [小，中，大] 即左儿子小于当前节点值，右儿子大于当前节点值。使用递归的方式找到第一个为空的节点，即是插入的位置。
复杂度分析:
时间复杂度O(n)
空间复杂度O(n)

/**
 * 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}
 */
var insertIntoBST = function(root, val) {
    if(root === null) return new TreeNode(val);
    if(val > root.val ){
        root.right =  insertIntoBST(root.right,val);
    }
    else if(val < root.val){
        root.left =  insertIntoBST(root.left,val);
    }
    return root;
};