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

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
输入数据保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
�
二叉搜索树特点：
1）左子树所有的节点值都比根节点的值小
2）右子树所有的节点值都比根节点的值大

若要插入一个新的节点，则需要先找到需要插入的位置：
1）如果值比当前节点值小，则继续往左子树找
2）如果值比当前节点值大，则继续往右子树找
3）如果树为空，则表示已经找到位置

而要搜索一棵二叉搜索树，可以利用二叉搜索树特点通过二分查找进行查找：

/**
 * 二叉搜索树的搜索
 *
 * @param root
 * @param target
 * @return
 */
public TreeNode searchBST(TreeNode root, int target) {
    if (root == null) {
        return null;
    }
    // 去左子树搜索
    if (target < root.val) {
        return searchBST(root.left, target);
    }
    // 去右子树搜索
    if (target > root.val) {
        return searchBST(root.right, target);
    }
    // 返回目标节点
    return root;
}

�那么如果需要插入一个节点，则可先找到位置，然后创建一个新的树

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        // 表示子树为空，已经找到位，作为新的子树
        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;
}