代码随机化刷新 - 二进制树 - 6.二叉搜索树的修改和构建

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

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

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

代码：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置返回待插入节点
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            // 插入节点操作，insertIntoBST函数返回值就是待插入节点
            root.right = insertIntoBST(root.right, val);
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        // 返回根节点给上一层
        return root;
    }
}

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

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

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

代码：

1.代码随想录解法：左子树添加到右子树最左边，返回删除节点右孩子为新的当前根节点

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //分为五种情况：
        // 1.未找到，直接返回root
        if (root == null) return root;
        if (root.val == key) {
            // 2.找到的节点左子树为空，右子树非空，右子树补上
            if (root.left == null && root.right != null) {
                return root.right;
                // 3.找到的节点右子树为空，左子树非空，左子树补上
            } else if (root.left != null && root.right == null) {
                return root.left;
                // 4.找到的节点左右子树都为空，直接删除
            } else if (root.left == null && root.right == null) {
                return null;
                // 5.找到的节点左右子树都非空，左子树添加到右子树最左边，
                // 返回删除节点右孩子为新的根节点
            } else {
                TreeNode node = root.right;
                while (node.left != null) {
                    node = node.left;
                }
                node.left = root.left;
                return root.right;
            }
        }
        if (root.val > key) root.left = deleteNode(root.left, key);
        if (root.val < key) root.right = deleteNode(root.right, key);
        return root;
    }
}

2.labuladong 解法：右子树最小节点替换待删节点，再把待删节点删了

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            // 这两个 if 把情况 1 和 2 都正确处理了
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // 处理情况 3
            // 获得右子树最小的节点
            TreeNode minNode = getMin(root.right);
            // 删除右子树最小的节点
            root.right = deleteNode(root.right, minNode.val);
            // 用右子树最小的节点替换 root 节点
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) node = node.left;
        return node;
    }
}

31-669.修剪二叉搜索树????

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

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

链接：669. 修剪二叉搜索树

代码：

class Solution {
    // 函数定义：满足区间返回root，不满足则返回root的符合条件的子节点
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            // 当前节点比low小那就去右边寻找符合区间[low, high]的节点
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // root.left接入符合条件的左孩子
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

32-108.将有序数组转换为二叉搜索树????

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。

链接：108. 将有序数组转换为二叉搜索树

代码：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }

    // 左闭右闭区间[left, right]
    // 函数定义：根据数组和给定区间构造root的左右节点
    private TreeNode traversal(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = left + ((right - left) >> 1); // 防止溢出
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}

33-538.把二叉搜索树转换为累加树????

题目：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

链接： 538. 把二叉搜索树转换为累加树

代码：

class Solution {
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }
    
    int sum = 0;

    // 右中左遍历，累加节点的值
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.right);
        // 维护累加和
        sum += root.val;
        // 将 BST 转化成累加树
        root.val = sum;
        traverse(root.left);
    }
}