代码随想录第二十天|二叉树part08--669.修建二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

刷题小记：

上期学习了二叉搜索树的插入和删除操作，这次学习如何按区间修剪二叉搜索树。还有两题，关于借助二叉搜索树的有序特性进行转换。

669.修剪二叉搜索树（669.修剪二叉搜索树）

题目分析：

给定一个二叉搜索树的根节点root，以及最小边界low和最大边界high，通过修建二叉搜索树，使得所有节点的值在[low, high]之中。并保证不改变保留在树中元素的相对结构。

解题思路：

在450.删除二叉搜索树中的节点一题中，我们已经研究了二叉搜索树节点的删除方式，在此题之中，我们同样也面临节点删除的情况，结合情景进一步分析如下：

小于下边界的节点，其左子树必然全部出界，均需剪枝；
大于上边界的节点，其右子树必然全部出界，均需剪枝。

只需反复运用这两条法制，并遍历整棵树，能够确保结果正确。

解题步骤：

考虑使用前序遍历的递归解决：

递归的参数：当前节点，下界，上界
递归的返回值：修剪后的当前节点所在子树的根节点
递归的终止条件：遇到空节点，返回null
递归的单层递归逻辑：

- 对于当前节点cur，如果cur.val<low，那么递归cur的右子树的修剪结果并直接返回
- 对于当前节点cur，如果cur.val>high，那么递归cur的左孩子的修剪结果并直接返回
- 递归修剪cur的左孩子
- 递归修剪cur的右孩子
- 返回修剪完毕的cur

java">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.将有序数组转换为二叉搜索树（108.将有序数组转换为二叉搜索树）

题目分析：

给定一个升序排列的整数数组nums，需将其转换成一棵平衡二叉搜索树（左右子树相差高度不超过1）。

解题重点：

构造方式：

观察题目示例发现，构造方式存在左倾式和右倾式两种。

左倾式：以大者为父节点，小者为左孩子节点。

右倾式：以小者为父节点，大者为右孩子节点。

此处我默认选择左倾式进行构造。

转换方式：

观察完构造方式，再来观察如何进行转换。

给定nums数组（包括过程中的子数组），要么长度为奇，要么为偶。

若为奇数组，则中间值为当前子树的根节点，以中间值（下标为n/2）为界的左子数组转换成左子树，右子数组转换成右子树
若为偶数组，由于先前采用了左倾式的构造方式（与奇数组情况统一），此处选择以下标为n/2处为中间值（数组长为n），则中间值为当前子树的根节点，以中间值为界的左子数组转换成左子树，右子数组转换成右子树

解题步骤：

构造前序遍历的递归函数traversal如下：

递归的参数：转换数组nums，左边界下标left，右边界下标right（左闭右闭）
递归的返回值：转换后所得子树的根节点root
递归的终止条件：left > right时，返回空节点null
递归的单层递归逻辑：

- 取mid = (right + left + 1) / 2，用下标为mid的值构造当前子树的根节点root
- 用new_left = left，new_right = mid - 1的区间构造左子树
- 用new_left = mid + 1，new_right = rigt的区间构造右子树
- 最终返回root。

java">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 = (right + left + 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);

        return root;
    }
}

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

题目分析：

给出一棵二叉搜索树的根节点root，该树的节点值均不相同，现要求将其转换成累加树——每个节点值的新值等于原树中大于等于原值的值之和。

解题思路：

大于等于原值的值，除自身的值相等外，无其他相等的值；而大于原值的其他值，出现在该值的“右侧”，根据二叉搜索树的特性，这个“右侧”描述为：该节点的最左祖先节点x，其父节点x_dad和x_dad的右子树的全部节点。

可知，欲将二叉搜索树转换成这种累加树，应当从原树的右下方开始运算，即右中左的顺序，即倒序的中序遍历，在该遍历顺序下，每一个中节点的值更改为原节点值+前缀节点值。

解题步骤：

采用右中左的遍历顺序，构造递归函数：

递归的参数：当前节点root
递归的返回值：更改后的节点
递归的终止条件：遇到空节点，返回null
递归的单层递归逻辑：

- 向右递归，更新累加后的“右节点”
- 若前缀节点pre不为空，则更新当前节点值累加上前缀节点pre的值，并更新前缀节点pre
- 向左递归，更新累加后的“左节点”
- 返回root

java">class Solution {
    TreeNode pre = null;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        
        root.right = convertBST(root.right);
        if (pre != null) root.val += pre.val;
        pre = root;
        root.left = convertBST(root.left);

        return root;
    }
}