LeetCode 刷题笔记 7：二叉搜索树 2

神马都会亿点点的毛毛张2026/1/25大约 6 分钟算法LeetCode二叉树LeetCode二叉树二叉搜索树递归迭代构造二叉树

题目1：701. 二叉搜索树中的插入操作

1.题目描述

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

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

示例 1：

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

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是 独一无二 的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

2.题解

题目2：450. 删除二叉搜索树中的节点

1.题目描述

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

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

2.题解

题目3：669. 修剪二叉搜索树

1.题目描述

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

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

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

树中节点数在范围 $[1, 10^4]$ 内
$0 <= Node.val <= 10^4$
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
$0 <= low <= high <= 10^4$

2.题解

2.1 递归法

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) return trimBST(root.right, low, high);
        if (root.val > high) return trimBST(root.left, low, high);

        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }
}

2.2 迭代法

题目4：108. 将有序数组转换为二叉搜索树

1.题目描述

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

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

2.题解

2.1 递归法

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

    public TreeNode traversal(int[] nums,int left,int right){
        if(left > right) return null;

        int mid = left + (right - left) / 2;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = traversal(nums,left,mid-1);
        cur.right = traversal(nums,mid +1,right);
        return cur;
    }
}

2.2 迭代法

题目5：538. 把二叉搜索树转换为累加树

1.题目描述

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

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

2.题解

解题思路：从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了

2.1 递归法

class Solution {
    // 声明一个变量 pre，用来记录遍历过程中节点的累加和
    int pre;

    // 主函数，将二叉搜索树转换为累加树
    public TreeNode convertBST(TreeNode root) {
        // 初始化 pre 为 0
        pre = 0;
        // 调用递归方法遍历树
        traversal(root);
        // 返回转换后的根节点
        return root;
    }

    // 递归方法遍历树，按从大到小的顺序更新节点值
    // 1. 确定形参和返回值：形参是当前节点 cur，返回值是 void，因为我们直接修改节点值
    public void traversal(TreeNode cur) {
        // 2. 确定终止条件：如果当前节点为空，则返回
        if (cur == null) return;

        // 3. 确定单层递归逻辑：首先递归右子树，确保从大到小的顺序
        traversal(cur.right);
        pre += cur.val;// 计算当前节点的累加和：pre保存了当前节点右子树及当前节点的累加和
        cur.val = pre;// 更新当前节点的值为累加和
        traversal(cur.left);// 递归左子树，继续更新左侧节点
    }
}

2.2 迭代法

class Solution {
    public TreeNode convertBST(TreeNode root) {
        int pre = 0;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.right;//右
            }else{
                cur = stack.pop();  //中
                pre += cur.val;
                cur.val = pre;
                cur = cur.left;   //左
            }
        }
        return root;
    }
}