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

68 阅读 0 评论 45 点赞

我是靠谱客的博主自然大叔，最近开发中收集的这篇文章主要介绍代码随想录算法训练营第二十二天 | 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

二叉搜索树考虑是有序的，最近祖先要不是本身要不就是两个节点的区间[p,q]，对于所有的左子树都小于结点值，所有的右子树都大于结点值。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val&&root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        return root;
        
    }
}

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

给定二叉搜索树（BST）的根节点 root和要插入树中的值 value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

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

思路一：迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode pre=root;
        TreeNode newroot=root;
        if(root==null) return new TreeNode(val);
        while(root!=null){
            pre=root;
            if(root.val>val){
                root=root.left;
            }else if(root.val<val){
                root=root.right;
            }
        }
        if(pre.val>val){
            pre.left=new TreeNode(val);
        }else{
            pre.right=new TreeNode(val);
        }
        return newroot;
    }
}

思路二：递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) return new TreeNode(val);
        if(root.val>val){
            root.left=insertIntoBST(root.left,val);
        }else if(root.val<val){
            root.right=insertIntoBST(root.right,val);
        }
        return root;
    }
}

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]

删除儿茶搜索树的某结点有以下几种可能：

没有找到删除节点，遍历到root==null 直接返回
可以找到删除节点

①左右节点均为空，直接删除节点返回空节点

②左子树为空，右子树不为空，删除节点右子树补位

③右子树为空，左子树不为空，删除节点左子树补位

④左右子树均不为空，首先寻找得到右子树的最左边节点，将删除节点的左子树节点放到后面，返回删除节点右孩子为新的根节点。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root=delete(root,key);
        return root;
    }
    public TreeNode delete(TreeNode root,int key){
        if(root==null) return null;
        if(root.val>key){
            root.left=delete(root.left,key);
        }else if(root.val<key){
            root.right=delete(root.right,key);
        }else{
            //左边为空返回右边
            if(root.left==null) return root.right;
            //右边为空返回左边
            if(root.right==null) return root.left;
            //寻找删除节点右子树的最左边点
            TreeNode temp=root.right;
            while(temp.left!=null){
                temp=temp.left;
            }
            //将删除节点赋值右子树的最左边点
            root.val=temp.val;
            root.right=delete(root.right,temp.val);
        }
        return root;
    }
}