算法训练营day22 | {669.修剪二叉搜索树, 108.将有序数组转换为二叉搜索树, 538. 把二叉搜索树转换为累加树}

第六章二叉树part08，二叉搜索树的修改和改造。

669. 修剪二叉搜索树

1.1 解题分析

  • 本题的重点也在讨论节点的终止条件上，不过和上一题不同，需要完整遍历一整个树，不能遇到要删除的节点就返回。相反，要利用二叉搜索树的价值，能在当前节点就判断整棵子树的命运，实现剪枝。

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 形参就是父递归给子递归的约束，然后返回修剪后的树的根节点。
    2. 确定递归的终止条件。 如果当前遍历到了根节点，则返回null；如果遇到要删除的节点，继续递归判断可能符合区间条件的子树。
    3. 确定单层递归的逻辑。 前序遍历，中左右，其实没有中的处理逻辑，重点在终止条件的处理上。

  • 前序遍历-递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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;
        }
    }

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

2.1 解题分析

  • 数组的区间下标左闭右闭。

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 需要传入一个升序的整数数组，构造树的数组起始下标，终止下标，返回一个TreeNode；
    2. 确定递归的终止条件。 当数组起始下标 > 终止下标时，返回null。
    3. 确定单层递归的逻辑。 前序遍历，中左右，当前数组的长度/2 即为根节点元素所在位置，以此为分割线，划分左子树区间和右子树区间。

  • 前序遍历-递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return buildBST(nums, 0, nums.length - 1);
        }

        public TreeNode buildBST(int[] nums, int left, int right) {
            if (left > right) return null;
            int rootIndex = left + (right - left) / 2;
            TreeNode root = new TreeNode(nums[rootIndex]);
            root.left = buildBST(nums, left, rootIndex - 1);
            root.right = buildBST(nums, rootIndex + 1, right);
            return root;
        }
    }

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

3.1 解题分析

  • 暴力的方法是先遍历一遍获取一个树的totalSum，接着再中序遍历一遍，本轮的cuSum重新开始累加，然后遍历到哪个节点，就更新它的值为（totalSum - curSum）。

  • 能不能只遍历一遍呢？那必须从后往前遍历，也就是右中左，并且反中序遍历这个二叉树，然后顺序累加即可。

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 形参需要传入一个根节点，无需返回值，此外需要定义一个全局变量整数型pre，用于记录前一个结点的值。
    2. 确定递归的终止条件。 如果当前遍历到空节点，则返回null。
    3. 确定单层递归的逻辑。 反中序遍历，右中左，中：如果pre没有被赋值，给pre赋值，否则给pre加上当前值，然后更新当前节点的值。

  • 反中序遍历-递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
        int pre = 0;
        public TreeNode convertBST(TreeNode root) {
            reverseInOrder(root);
            return root;
        }

        public void reverseInOrder(TreeNode node) {
            if (node == null) return;
            reverseInOrder(node.right);
            pre += node.val;
            node.val = pre;
            reverseInOrder(node.left);
        }
    }

4. 二叉树章节总结

  • 二叉树：总结篇！（需要掌握的二叉树技能都在这里了）

  • 33道题目，包含普通二叉树、二叉搜索树，可以看看打卡的博客回顾一下这8天做过的题目。

    • 什么样的题目适合什么遍历方式？
    • 递归三步曲如何分析？
    • 递归函数什么时候需要返回值，什么时候不需要？
    • 递归函数什么需要回溯，什么时候不需要？
    • 递归函数什么时候需要定义全局变量，什么时候不需要？

  • 涉及构造一个二叉树，无论是普通的二叉树还是二叉搜索树，一定是前序遍历，先构造根节点。

  • 求普通二叉树的属性，一般是后序遍历，一般要通过递归函数的返回值做计算。

  • 求二叉搜索树的属性，一定是中序遍历，不然浪费有序的特性。

  • 学习时长：2小时

Leetcode > 二叉搜索树
#Java #代码随想录
算法训练营day22 | {669.修剪二叉搜索树, 108.将有序数组转换为二叉搜索树, 538. 把二叉搜索树转换为累加树}
http://paopaotangzu.xyz/cn/day22_leetcode/
作者
PROTON TANG
发布于
2026年1月7日
许可协议