题目与题解
参考资料：二叉树总结
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.将有序数组转换为二叉搜索树
解题思路：
平衡二叉树的定义是每个节点左右子树的高度差都不大于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;
}
}遇到的困难
写的时候没有想到可以换成有序数组去思考，一开始想着root的结果就是右边所有节点的和加上val，左边节点则是中间节点加上左边的val，写着写着就乱起来了。凡是遇到二叉搜索树并且要对每个节点进行有序操作的，一定要先看看能不能从升序序列考虑，问题就清晰了。
今日收获
再次熟悉了一下二叉树的操作，终于结束了。
一般而言，二叉树的题目规律如下：
涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。
涉及到父子节点，一般用前序，方便父节点指向子节点。
二叉树的题目看起来变化很大，其实无非就是递归，迭代方法，中间根据情况夹杂着回溯，涉及到前中后序三种遍历，万变不离其宗。希望二刷的时候所有方法都能掌握吧。