代码随想录算法训练营第22天|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

一、力扣235.二叉搜索树的最近公共祖先

1.1 题目

在这里插入图片描述

1.2 思路

利用二叉搜索树的有序特性来实现：
如果cur大于pq：向左搜索；
如果cur小于pq：向右搜索；
如果介于两者之间：则找到！

1.3 代码

递归法：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归法
        if(root == null){
            return null;
        }
        return traversal(root,p,q);
    }
    public TreeNode traversal(TreeNode root,TreeNode p,TreeNode q){
        //和上题类似，第二种情况也包含在了处理逻辑里
        if(root.val < p.val && root.val < q.val){
            return traversal(root.right,p,q);
        }
        if(root.val > p.val && root.val > q.val){
            return traversal(root.left,p,q);
        }
        //当前节点介于[p,q]  闭区间
        return root;
    }
}

迭代法：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //迭代
        if(root == null){
            return null;
        }
        TreeNode cur = root;
        while(true){
            if(cur.val > p.val && cur.val > q.val){
                cur = cur.left;
                continue;
            }
            if(cur.val < p.val && cur.val < q.val){
                cur = cur.right;
                continue;
            }
            return cur;
        }
        
    }
}

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

2.1 题目

在这里插入图片描述

2.2 思路

根据二叉搜索树的特性，比大小向下遍历，直到找到null，将其new一个新的结点插入进去。

2.3 代码

自己的思路：

class Solution {
    public TreeNode newnode;
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //比大小来遍历寻找该插入的位置
        if(root == null){
            return new TreeNode(val);
        }
        traversal(root,val);
        return root;

    }
    public void traversal(TreeNode root,int val){
        if(val > root.val){
            if(root.right == null){
                newnode = new TreeNode(val);
                root.right = newnode;
                return;
            }
            traversal(root.right,val);
        }
        if(val < root.val){
            if(root.left == null){
                newnode = new TreeNode(val);
                root.left = newnode;
                return;
            }
            traversal(root.left,val);
        }
    }
}

三、力扣450.删除二叉搜索树中的节点

3.1 题目

在这里插入图片描述

3.2 思路

梳理本题的五种情况：
（1）没有找到该节点
（2）找到了该节点，该节点的左右孩子均为空
（3）找到了该节点，该节点的左孩子为空，右孩子不为空
（4）找到了该节点，该节点的左孩子不为空，右孩子为空
（5）找到了该节点，该节点的左右孩子均不为空（最关机键的点）：见下图

3.3 代码

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //确定递归的终止条件
        //没有找到该节点
        if(root == null){
            return null;
        }
        //找到了该节点
        if(root.val == key){
            if(root.left == null && root.right == null){
                return null;
            }else if(root.left != null && root.right == null){
                return root.left;
            }else if(root.left == null && root.right != null){
                return root.right;
            }else{
                //假设root的右子树上位,那么需要将root的左子树插入root的右子树中，再返回右子树
                TreeNode cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                return root.right;
            }
        }

        //单层递归逻辑
        if(key > root.val){
            root.right = deleteNode(root.right,key);
        }
        if(key < root.val){
            root.left = deleteNode(root.left,key);
        }
        return root;
    }
}