代码随想录:二叉树29-30

时间:2024-04-30 07:23:02

目录

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

题目

代码(迭代法走一边)

代码(递归法走一边)

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

题目

代码(递归法走一边)


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

题目

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

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入: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 = null;
        TreeNode cur = root;

        //如果树为空,单独处理(这个不能漏,不然后面pre.val编译会出错)
        if(root == null){
            return new TreeNode(val);
        }

        //不断进行左右子树判断,使得pre指向插入节点的父节点,cur正好为null
        while(cur != null){
            if(cur.val > val){
                pre = cur;
                cur = cur.left;
            }
            else if(cur.val < val){   //注意这里必须有else,不然会出错因为cur会改变
                pre = cur;
                cur = cur.right;
            }
        }
        TreeNode newNode = new TreeNode(val);
        //如果父节点小,就往左子树插入
        if(pre.val > val){
            pre.left = newNode;
        }
        //如果父节点大,就往右子树插入
        else{
            pre.right = newNode;
        }
        return root;  //返回根节点
    }
}

代码(递归法走一边)

class Solution {
    //遍历的逻辑是自上而下,根据val的大小往一个左or右子树走
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //终止条件,说明root已经走到插入元素的节点位置了
        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 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

示例 1:

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

代码(递归法走一边)

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //终止条件
        if(root == null){
            return null;
        }
        
        //走一边单层逻辑(自上而下递归)
        //如果key比root中值小,说明要修改左子树,往左子树走
        if(root.val > key){
            root.left = deleteNode(root.left,key); //修改左子树指针 
        }
        //如果key比root中值大,说明要修改右子树,往右子树走
        if(root.val < key){
            root.right = deleteNode(root.right,key); //修改右子树指针
        }
        //如果key等于root中值,说明找到了删除节点
        if(root.val == key){
            //情况1:删除节点root是叶子节点
            if(root.left == null && root.right == null){
                return null;  //返回null,代表直接删除root
            }
            //情况2:删除节点root只有左子树
            else if(root.left != null && root.right == null){
                return root.left;  //返回其左子树,代表删除了root
            }
            //情况3:删除节点root只有右子树
            else if(root.left == null && root.right != null){
                return root.right; //返回其右子树,代表删除了root
            }
            //情况4:删除节点root有左右子树
            else{
                TreeNode cur = root.right;  //cur是删除节点的右孩子
                while(cur.left != null){
                    cur = cur.left;  //cur一直走到最左下节点
                }
                cur.left = root.left;  //把删除节点的左子树挂到删除节点右子树的最左下角
                return root.right; //返回其右子树,代表删除了root,且删除节点的左子树已经挂到右子树了
            }
        }
        return root;  //返回根节点
    }
}