《代码随想录》Day21打卡！
写在前面：祝大家新年快乐！！！2025年快乐，2024年拜拜~~~
《代码随想录》二叉树：修剪二叉搜索树
本题的完整题目如下：
本题的完整思路如下： 1.本题使用递归进行求解，所以分为三部曲： 2.第一步：确定递归函数的参数和返回值：参数是二叉树的节点和要删除节点的范围。所以使用主方法作为递归函数。 3.第二步：确定递归的终止条件：当当前节点为空时，返回null 3.第三步：确定单次递归函数的逻辑：当当前节点的值小于下限时，说明当前节点的左子树都不满足要求，所以递归处理当前节点的右子树即可。当当前节点的值大于上限时，说明只有当前节点的右子树都不满足要求，左子树才可能会有要保留的节点，那么此时递归当前节点的左子树即可。最后一种情况就是当前节点满足给出的范围，那么此时该节点需要被保留，不对当前节点进行任何处理，所以递归当前节点的左子树并赋值给当前节点的左节点，再递归当前节点的右子树，并赋值给当前节点的右节点。 4.本题的难点是，当有一个子树都不满足要求时，则直接处理该节点的另一个子树即可。当当前节点满足要求时，不需要对当前节点进行处理，递归处理当前节点的左子树和右子树。 本题的完整代码如下：
//669. 修剪二叉搜索树
class Solution37 {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null){return null;}if(root.val < low){return trimBST(root.right, low, high);}else if(root.val > high){return trimBST(root.left, low, high);}else{root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}
《代码随想录》二叉树：将有序数组转换为二叉搜索树
本题的完整题目如下：
本题的完整思路如下： 1.本题是将有序数组转换为二叉搜索树，所以数组中间的元素就是根节点的值，将数组将中间元素分开，分为左右两个部分，左边的就是左子树的部分，右边的是右子树的部分。所以也是使用递归来做： 2.第一步：确定递归函数的参数和返回值：参数是原数组以及左边界和右边界，返回值是二叉树的根节点。 3.第二步：确定递归函数的终止条件：当左边界大于等于右边界时，终止。 3.第三步：确定单次递归函数的逻辑：首先取出当前边界范围内数组的中间的索引值mid。将该索引值对应的元素作为值创建一个节点，该节点的左子树为递归结果，其中递归函数的参数为：left=left，right=mid-1。该节点的右子树为递归结果，其中递归参数是：left=mid+1，right=right。最后返回当前节点。 4.本题也较为难，需要使用IDEA debug一下该方法的递归过程，很难想到最后是如何构建该二叉搜索树的。 本题的完整代码如下：
//108.将有序数组转换为二叉搜索树
class Solution38 {public TreeNode sortedArrayToBST(int[] nums) {return sorted(nums, 0, nums.length - 1);}public TreeNode sorted(int[] nums, int left, int right) {if(left > right){return null;}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = sorted(nums, left, mid -1);root.right = sorted(nums, mid + 1, right);return root;
}
}
《代码随想录》二叉树：把二叉搜索树转换为累加树
本题的完整题目如下：
本题的完整思路如下： 1.首先，本题也是使用递归进行求解。 2.第一步：确定递归函数的参数和返回值：参数是二叉树节点，返回值二叉累加树的根节点，定义一个全局变量，记录累计值，所以使用主方法作为递归函数即可。 2.第二步：确定递归函数的终止条件：当当前节点为空时，返回。 3.第三步：确定单次递归函数中的逻辑：因为是二叉搜索树，右子树的左右节点都比左子树大，所以先处理右子树。所以递归当前节点的右子树，接着将当前节点的值累加到全局变量中。并将该值赋值给当前节点的值。接着，递归处理左子树即可。最后返回节点。 4.本题重点是，先处理右子树，并记录累加和，接着赋值，再处理左子树。思路简单，但是处理起来还是很难想到递归的过程。 本题的完整代码如下：
//538.把二叉搜索树转换为累加树
class Solution39 {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
return root;
}
}