每日一练：LeeCode-701、二叉搜索树中的插入操作【二叉搜索树+DFS+全搜】

本文是力扣每日一练：LeeCode-701、二叉搜索树中的插入操作【二叉搜索树+DFS+全搜】学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

给定二叉搜索树（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]

提示：

树中的节点数将在 [0, 104]的范围内。
-10^8 <= Node.val <= 10^8
所有值 Node.val 是独一无二的。
-10^8 <= val <= 10^8
保证 val 在原始BST中不存在。

思路

题目要求：返回任意有效的结果即可
所以，只要按照⼆叉搜索树的规则去遍历，遇到空节点就插⼊节点就可以了

递归

1、确定递归函数参数以及返回值

需不需要返回值取决于，题目实现递归函数的难度，本题有返回值的话，可以利⽤返回值完成新加⼊的节点与其⽗节点的赋值操作

	TreeNode traversalInsert(TreeNode cur, int val)

2、确定终⽌条件
终止条件：遇到空节点

     if (cur==null){
         TreeNode node = new TreeNode(val);
         return node;
     }

3、确定单层递归的逻辑
1)由于这颗树是二叉搜索树，中序遍历跑不了的，由于没有中间逻辑，所以直接左->右 即可
2)由于需要搜索到适合 插入值的位置,正好利用二叉搜索树的特性（左中右水平递增）即可

        if (cur.val > val){
            cur.left = traversalInsert(cur.left,val);
        }
        if (cur.val < val){
            cur.right = traversalInsert(cur.right,val);
        }
        return cur;

通过递归函数返回值完成了新加⼊节点的⽗⼦关系赋值操作了，下⼀层将加⼊节点返回，本层⽤root.left或者root.right将其接住

完整代码

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return traversalInsert(root,val);
    }

    TreeNode traversalInsert(TreeNode cur, int val){
        if (cur==null){
            TreeNode node = new TreeNode(val);
            return node;
        }
        if (cur.val > val){								//左
            cur.left = traversalInsert(cur.left,val);
        }
        if (cur.val < val){								//右
            cur.right = traversalInsert(cur.right,val);
        }
        return cur;
    }

}