代码随想录Day21：二叉树（修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树——全递归版本以及总结）

669修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

• 树中每个节点的值都是 唯一 的

思路：基础思路就是删除二叉树中的节点

错误想法：递归处理，然后遇到 root->val < low || root->val > high 的时候直接return NULL，一波修改，赶紧利落。

//C++版本错误代码，主要就是理解思路
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr || root->val < low || root->val > high) return nullptr;root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};

然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树。过早地进行判断可能会导致不应该删除的分支被删除。

本题与删除BST节点的不同之处？通义大模型-参考

本题（修剪二叉搜索树）与删除二叉搜索树（BST）中的节点虽然都涉及到对树结构的修改，但它们的目标和操作方式有着本质的区别。以下是两者之间的主要不同点：

1. 目标不同
修剪BST：目的是将所有不在给定范围 [low, high] 内的节点从树中移除，同时保持剩余节点的相对结构不变。这意味着你可能需要移除一个节点及其一部分子树，并且这种移除可能是连续的（即一个节点被移除后，其部分或全部祖先节点也可能因为不满足条件而被移除）。
删除BST中的节点：目标是移除树中的一个特定节点，并确保在删除该节点之后，BST 的性质仍然得到保持（即对于每个节点，左子树的所有节点值小于它，右子树的所有节点值大于它）。删除操作通常涉及处理三种情况：要删除的节点没有子节点、只有一个子节点、有两个子节点。
2. 操作方式不同
修剪BST：通过递归遍历整个树来实现。如果当前节点不符合条件，则根据 BST 的性质决定是保留左子树还是右子树进行进一步的检查和修剪。这个过程可能会导致连续地“跳过”一系列节点，直到找到符合范围的节点为止。
删除BST中的节点：需要定位到特定的节点并根据它是否有子节点及子节点的数量采取不同的策略来维持 BST 的结构。例如，如果要删除的节点有两个子节点，那么通常会寻找它的前驱或后继节点（即左子树的最大值或右子树的最小值），将其值复制到要删除的节点位置，然后删除前驱或后继节点。
3. 结果的不同
修剪BST：最终结果是一个新的 BST，其中所有节点的值都在指定范围内，且原始树中未被移除节点的相对结构得到了保持。
删除BST中的节点：只影响被直接删除的那个节点以及必要的时候调整与其相关的节点（如上述提到的前驱或后继节点），其余部分的树结构基本保持不变。

总结来说，尽管两个操作都涉及到改变树的结构，但它们关注的重点不同：修剪是关于范围过滤，而删除是关于精确移除某个节点并保持BST的性质。因此，两种操作的具体实现也大相径庭。

package org.example.Tree;public class trimBST669 {public TreeNode trimBST(TreeNode root, int low, int high) {TreeNode result=traversal(root,low,high);return result;}private TreeNode traversal(TreeNode root, int low, int high) {if(root==null)return null;if (root.val > high) {// 当前节点和右子树都不合法，只保留左子树继续处理return traversal(root.left, low, high);}if (root.val < low) {// 当前节点和左子树都不合法，只保留右子树继续处理return traversal(root.right, low, high);}// 当前节点合法，继续处理左右子树root.left = traversal(root.left, low, high);root.right = traversal(root.right, low, high);return root;}}

package org.example.Tree;public class sortedArrayToBST108 {public TreeNode sortedArrayToBST(int[] nums) {TreeNode root=traversal(nums,0,nums.length-1);return root;}//left分别为区间左边界, right右边界//注意，traversal区间都统一设置为左闭右开//left=right也需要继续构造private TreeNode traversal(int[] nums,int left,int right){if(left>right)return null;int mid=(left+right)/2;TreeNode temp=new TreeNode(nums[mid]);//left,注意左边遍历最后的结果要变为分支temp.left=traversal(nums,left,mid-1);//righttemp.right=traversal(nums,mid+1,right);return temp;}
}

package org.example.Tree;public class convertBST538 {TreeNode pre=null;public TreeNode convertBST(TreeNode root) {traversal(root);return root;}//中序遍历变体，右-中-左private void traversal(TreeNode root) {if(root==null)return;traversal(root.right);//pre为null的话就说明是第一个节点，也就是最大的那个，不用变if(pre!=null)root.val= root.val+ pre.val;pre=root;traversal(root.left);}
}