每日一题~二叉搜索树中的插入操作

题目链接：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

题目描述：

思路分析：由题可知，题目的要求是给我们一个二叉搜索树和一个 val，将这个 val 插入到二叉搜索树中，并且这个树仍然是二叉搜索树。题目中给了两个插入方式，第一种是将 val 插入到原来没有节点的位置；第二种是，将 val 替换掉已经存在的节点，然后重新调整树。通过观察发现第一种方法比第二种更加简单，所以我们接下来就根据第一种方法进行解答。

插入 val 节点总共需要两步：

1、寻找 val 节点插入的位置， 因为题目中的树是一个二叉搜索树，所以如果 root.val < val ，那么 val 应该插到右子树那边，我们只需要在右子树中再寻找合适的位置就可以了，如果 root.val > val, 那么从左子树中再寻找位置就可以。

2、插入 val 节点，如何确定这个位置是我们要找的位置呢？由第一步可以知道，我们是从 root 节点开始向下找，所以当 root = null 时，说明我们已经找到了那个位置，这时候我们直接返回到上一个节点，如果此时 root.left == null && root.val > val，那么直接将 val 添加到 root.left 就可以，注意右边的情况和左边判断时一样，不能直接使用 else，如果直接使用 else，那么在回溯到中间的时候会将 val 重新添加到其他节点的右子树。

代码示例：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        search(root,val);
        return root;
    }
    public void search(TreeNode root,int val) {
        if(root == null) return;
        if(root.val > val) {
            // 在左子树继续寻找
            search(root.left,val);
        }else {
            search(root.right,val);
        }
        if(root.left == null && root.val > val) {
            root.left = new TreeNode(val);
        }else if(root.right == null && root.val < val){
            root.right = new TreeNode(val);
        }
       
    }
}