代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，538.把二叉搜索树转换为累加树，总结篇

题目与题解

参考资料：二叉树总结

669. 修剪二叉搜索树

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

代码随想录题解：669. 修剪二叉搜索树

视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树_哔哩哔哩_bilibili

解题思路：

有了昨天删除二叉搜索树节点的题目为基础，这一题只是从删除一个特定节点改为删除多个符合条件的节点，做法是类似的。

这里还是用递归做，入参是根节点，low和high，终止条件是节点为空，返回值为完成删除后的根节点。递归体为：如果根节点的值在范围内，则分别对其左右子树进行递归，得到新的左右子树根节点；如果根节点的值在范围外，分情况讨论：如果该节点是叶子节点，直接返回null；如果左子树为空，或者其值小于low，则对右子树进行递归，并让根节点等于递归后的结果；如果右子树为空，或者其值大于high，则对左子树进行递归，并让根节点等于递归后的结果。

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

看完代码随想录之后的想法

思路差不多，随想录写的更精简一点。有些代码是可以合并的，比如并不需要在root.val不满足条件时判断左右子树是否为空，直接根据其小于low还是大于high进行下一层的递归即可，并且可以把val不在区间内的情况写在前面，就可以提前return了。

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在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

遇到的困难

如何考虑到所有的情况是个难点，好在有昨天的题打底稍微好一些。

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

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

代码随想录题解：108.将有序数组转换为二叉搜索树

视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树_哔哩哔哩_bilibili

解题思路：

平衡二叉树的定义是每个节点左右子树的高度差都不大于1，以此达到搜索效率最高的结果。那么在构造的时候，就要尽量让左右子树中含有的节点数量不要相差太大，所以每次把数组最中间的节点当作根节点最好，这样也符合二叉搜索树的要求，即左边的数小于根节点，右边的数大于根节点。

这里用递归来做，递归入参是有序数组，对应的起始位置low和终止位置high（java不能直接传地址，所以为了不额外new数组就用下标来标识本次递归的数组范围），这里low和high是表示闭区间[low, high]，终止条件是low >= high或low小于0或high大于数组最大下标，返回值是建立的二叉搜索树根节点。递归体为：如果low > high，返回空，如果low=high，返回值为nums[low]的新节点，剩下的情况里，将数组一分为二，取得根节点的位置indexRoot = (low+high)/2，再递归的将数组左边的数和右边的数分别传入递归函数，得到左右子树的结构。

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

	public TreeNode sortedArrayToBST(int[] nums, int low, int high) {
		if (low < 0 || high >= nums.length || low > high) return null;
		if (low == high) return new TreeNode(nums[low]);
		int indexRoot = (low + high)/2;
		TreeNode root = new TreeNode(nums[indexRoot]);
		root.left = sortedArrayToBST(nums, low, indexRoot - 1);
		root.right = sortedArrayToBST(nums, indexRoot + 1, high);
		return root;
	}
}

看完代码随想录之后的想法

如随想录所说，这题本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。思路是一样的，还是写法上可以精简，low=high的情况可以不用判断，后面的已经涵盖了，并且low和high输入时候已经确定了最大边界，二者不会超出边界，所以不用判断low<0和high > 最大下标。

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

遇到的困难

边界条件略微需要注意一下，题本身不难。

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

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

代码随想录题解：538.把二叉搜索树转换为累加树

视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树_哔哩哔哩_bilibili

解题思路：

凡是遇到二叉搜索树里面，跟升序序列有关的题，都可以先转换成数组去思考如果是有序数组应该怎么做，然后再多加一步遍历二叉搜索树得到有序序列的过程，边遍历边计算出相应的结果。但是自己做的时候被绕晕了，没有写出来。

看完代码随想录之后的想法

这道题变成数组，就是求从最大数到最小数的累加和，比如对于一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]。做法也就很明确了，应该按照右中左的顺序来遍历，并累加求和。为此在递归或迭代时，需要记录一下前一个节点的累加和，方便计算当前节点的累加和。

class Solution {
	int pre = 0;
    public TreeNode convertBST(TreeNode root) {
		if (root == null) return root;
		convertBST(root.right);
		root.val += pre;
		pre = root.val;
		convertBST(root.left);
		return root;
    }
}