LeetCode刷题日记之二叉树（七）

前言

又是学习LeetCode二叉树的新一天，今天还是继续学习一下二叉搜索树的内容，二叉树的基本内容快学习的差不多啦，希望博主记录的内容能够对大家有所帮助 ，一起加油吧朋友们！💪💪💪

二叉搜索树中的插入操作

LeetCode题目链接

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

思路梳理🤔🤔

• 题目中虽然提到了存在多种有效的插入方式，但是我们可以就以遍历找到对应位置插入节点即可🤔

递归三要素梳理🤔🤔

• 确定递归的参数和返回值

//这里的返回值可以有也可以没有，我们先给出有的思路，有返回值即直接返回一个TreeNode
//参数的话就是要插入的树根节点和要插入的值
public TreeNode insertIntoBST(TreeNode root, int val) {}

• 确定递归的出口

//遍历到插入位置null时直接返回插入节点，等下处理左右子树的时候直接让root.left = 返回节点即可🤔
if(root == null){ //找到位置插入节点
    TreeNode node = new TreeNode(val);
    return node;
}

• 确定递归的单层处理逻辑

//即判断当前节点值和要插入值大小进而往左或者右子树去进行插入操作🤔
if(root.val > val){ //往左去插
    root.left = insertIntoBST(root.left, val);
}else if(root.val < val){ //往右去插
    root.right = insertIntoBST(root.right, val);
}
return root; //返回插完的树

有返回值的总的递归代码如下

 /**递归法有返回值 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        /*递归出口*/
        if(root == null){ //找到位置插入节点
            TreeNode node = new TreeNode(val);
            return node;
        }

        /*单层处理逻辑*/
        if(root.val > val){ //往左去插
            root.left = insertIntoBST(root.left, val);
        }else if(root.val < val){ //往右去插
            root.right = insertIntoBST(root.right, val);
        }
        return root; //返回插完的树
    }
}

• 而没有返回值则需要有一个变量来记录每一次遍历的节点的父结点，当往下一层处理时就可以对父结点的左右子节点进行插值操作🤔，无返回值的递归方法如下

/**递归法没有返回值 */
class Solution {
    TreeNode parent = new TreeNode(0); // 记录遍历节点的父结点
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){ // 提前结束
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }

    private void traversal(TreeNode root, int val){
        /*递归出口*/
        if(root == null){ //找到位置插入节点
            TreeNode node = new TreeNode(val);
            if(parent.val > val){
                parent.left = node;
            }else{
                parent.right = node;
            }
            return ;
        }

        /*单层处理逻辑*/
        parent = root;
        if(root.val > val)traversal(root.left, val);//往左去插
        if(root.val < val)traversal(root.right, val);//往右去插   
        return ; //返回
    }
}

• 而迭代法同理就是也要记录遍历节点的父结点进行记录追踪，然后循环找到遍历位置后对父结点进行插值操作🤔，迭代方法代码如下

/**迭代法 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){ //提前结束
            TreeNode node = new TreeNode(val);
            return node;
        }

        TreeNode parent = root;//记录当前节点的父结点
        TreeNode cur = root;
        while(cur != null){ //循环遍历节点找插入位置
            parent = cur;
            if(cur.val > val) cur = cur.left;
            else cur = cur.right;
        }
        TreeNode node = new TreeNode(val); //找到位置后根据父结点的值来判断插入方式
        if(val > parent.val) parent.right = node;
        else parent.left = node;
        return root;
    }
}

删除二叉搜索树中的节点

LeetCode题目链接

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。 返回二叉搜索树的根节点。

我们来梳理一下思路🤔🤔，我们重点就要搞清楚单层处理逻辑

• 第一种情况：递归没找到要删除的节点，遍历到空节点直接返回了

• 第二种情况：找到要删除的节点并且节点是叶子节点，直接删除返回根节点null

• 第三种情况：找到要删除的节点并且节点的左孩子为空，右孩子不为空，删除节点并让右孩子补位，返回右孩子为根节点

• 第四种情况：找到要删除的节点并且节点的右孩子为空，左孩子不为空，删除节点并让左孩子补位，返回左孩子为根节点

• 第五种情况：左右孩子都不为空，则将删除节点的左子树作为删除节点右子树的最左节点的左孩子🤔🤔

我们来梳理一下递归三要素🤔🤔

• 确定递归的返回值和参数

//要返回根节点，对应要传入要删的子树根节点和要删除的值
public TreeNode deleteNode(TreeNode root, int key) {}

• 确定递归的出口

/*递归出口（五种情况）*/
if(root == null) return root;//第一种情况
if(root.val == key){
	if(root.left == null && root.right == null) {//第二种情况
		return null;
	} else if(root.left == null){//第三种情况
		return root.right;
	} else if(root.right == null){//第四种情况
		return root.left;
	}else{//第五种情况
		TreeNode node = root.right;
		while(node.left != null){
			node = node.left;
		}
		node.left = root.left;
		root = root.right;
		return root;
	}
}

• 确定递归的单层处理逻辑

/*单层处理逻辑*/
if(root.val > key) root.left = deleteNode(root.left, key);
if(root.val < key) root.right = deleteNode(root.right, key);
return root;

迭代法的话有点复杂这里我们就不写了，感兴趣的话大家自己可以写一下🫡🫡🫡

修剪二叉搜索树

LeetCode题目链接

给一个二叉树并指定最小数值边界和最大数值边界，通过修剪二叉树使得二叉树的所有节点值在这个闭区间中，返回修剪好的二叉搜索树的根节点。

我们来思路梳理一下🤔🤔

• 从上图中可以看到如果单纯去判断if(root.val <low || root >high) return null 的话，则上图中修剪区间[5,10]的时候就只能剪出一个8了，所以这该怎么处理呢？🤔🤔就是在上图中修剪区间为[5,10]时如果剪掉0节点的时候它的右孩子不为空就也需要修剪，我们将其右孩子连接上其父结点继续修剪即可😮😮

我们进一步来梳理递归三要素

• 确定递归的参数和返回值

//与插入和删除二叉搜索树节点类似，这里有没有返回值都可以，但是有返回值更方便点，可以通过递归的返回值来移除节点
//参数就是要修剪的树和修剪边界
TreeNode trimBST(TreeNode root, int low, int high){}

• 确定递归的出口

//遍历节点修剪节点肯定不会是出口，就是肯定要修剪完整个树，所以递归的出口还是到空节点处理
if(root == null)return null;

• 确定递归的单层处理逻辑

if(root.val < low){//如果当前节点小于边界则应该修剪其右孩子并返回符合条件的头节点
	TreeNode right = trimBST(root.right, low, high);//这里是把root给剪掉了去处理root.right了
    return right;
}
if(root.val > high){//如果当前节点大于边界则应该修剪其左孩子并返回符合条件的头节点
	TreeNode left = trimBST(root.left, low, high);//这里是把root给剪掉了去处理root.left了
    return left;
}
/*节点值在边界中则处理其左右两孩子子树*/
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;//返回节点

递归完整代码如下

/**递归法 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null)return null;
        if(root.val < low){
	        TreeNode right = trimBST(root.right, low, high);//把root剪掉处理其右孩子
            return right;
        }
        if(root.val > high){
            TreeNode left = trimBST(root.left, low, high);//把root剪掉处理其右孩子
            return left;
        }
        /*节点值在边界中则处理其左右两孩子子树*/
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

我们来梳理下迭代法的处理方式🤔🤔

• 因为二叉搜索树是有序的，不需要用栈来存储节点。我们循环处理的话需要注意，因为涉及判断要不要把左孩子的右子树连接到上一层，所以相当于循环处理三层，首先找到一个边界内的头节点，然后修剪左孩子（相当于往小边界找，若找到比边界还小则把右孩子连接处理节点的父结点直到空节点），然后右孩子的修剪逻辑类似。

迭代代码如下

/**迭代法 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null)return null; //提前结束
        
        //首先是要找到在边界内的头节点
        while(root != null && (root.val < low || root.val > high)){
            if(root.val < low)root = root.right;//往右找
            else root = root.left;//往左走
        }
        TreeNode node = root;
        //处理左孩子
        while(node != null){
            while(node.left != null && node.left.val < low){
                node.left = node.left.right;//把右孩子连接到父结点
            }
            node = node.left; //继续往小了找
        }
        node = root;

        //处理右孩子
        while(node != null){
            while(node.right != null && node.right.val > high){
                node.right = node.right.left;//把右孩子连接到父结点
            }
            node = node.right; //继续往小了找
        }
        return root;
    }
}

总结

二叉树的内容基本就要学习的差不多了，还剩下一些，我们继续加油，后面开始回溯的基本内容的学习✊✊✊