Leetcode701/450/669之二叉搜索树的插入删除修剪

二叉搜索树的插入删除修剪

Leetcode701-二叉搜索树中的插入操作

• 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
• 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
• 输入：root = [4,2,7,1,3], val = 5
• 输出：[4,2,7,1,3,5]

    public TreeNode insertIntoBST(TreeNode root, int val) {
        return insert(root,val);
    }

    public TreeNode insert(TreeNode root,int val){
        if(root==null){
            return new TreeNode(val);
        }

        if(root.val>val){
            root.left=insert(root.left,val);
        }
        if(root.val<val){
            root.right=insert(root.right,val);
        }
        

        return root;
    }

Leetcode450-删除二叉搜索树中的节点

• 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
• 输入：root = [5,3,6,2,4,null,7], key = 3
• 输出：[5,4,6,2,null,null,7]

    public TreeNode deleteNode(TreeNode root, int key) {
        root=delete(root, key);
        return root;
    }

    private 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;
    }

Leetcode669-修剪二叉搜索树

• 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案
• 输入：root = [1,0,2], low = 1, high = 2
• 输出：[1,null,2]

 public TreeNode trimBST(TreeNode root, int low, int high) {
        return trim(root,low,high);
    }

    public TreeNode trim(TreeNode root,int low,int high){
        if(root==null){
            return null;
        }

        if(root.val<low){
            return trim(root.right,low,high);
        }
        if(root.val>high){
            return trim(root.left,low,high);
        }
        root.left=trim(root.left,low,high);
        root.right=trim(root.right,low,high);
        
        return root;
    }