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

小半 • 2023年2月3日上午10:53 • 技术随笔 • 阅读 170

题目：

思路：

利用BST左小右大的性质，选择合适的位置来放入新节点

1.如果当前结点中没有任何一个结点
①题目给的BST为空 ②递归至节点该放的位置时root为null，则return 新节点（递归终止条件）
2.如果当前树不为空，则从根结点开始：
2.1如果新结点的key＜当前结点的key，则继续找当前结点的左子结点；
2.2如果新结点的key＞当前结点的key，则继续找当前结点的右子结点；

递归三部曲：
1.要放入新节点，就要使某一个原节点的left或者right=新的节点，所以返回值是TreeNode ，
2.终止条件就是当root为null时，如果原二叉搜索树不为空，则当root为null即表示递归到了二叉树的末端，直接return new的新节点返回给上一个节点及完成insert
3.比较val和当前root大小，若val更大，则将val放入root.right去递归，反之。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
    // 利用左小右大性质
        if(root==null){ // 如果原本不存在节点，则返回要insert的节点
            return new TreeNode(val,null,null);
        }
        // if 控制递归（BST常见模板） 
        // 满足条件才去递归！
        if(val>root.val){ //val大于root，让val去root的右子树
            root.right=insertIntoBST(root.right,val);  // 接住新建的节点
        }else if(val<root.val){ //val大于root，让val去root的右子树
            root.left=insertIntoBST(root.left,val);   // 接住新建的节点
        }
        return root;
    }   
}