如果对递归没有深刻的理解，这道题有点难。简单地删除一个节点是不够的，它需要被修剪！修剪二叉搜索树链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/给定一棵二叉搜索树，同时给定最小边界L和最大边界R时间。通过对二叉搜索树进行剪枝，所有节点的值都在[L,R]中（R>=L）。您可能需要更改树的根，因此结果应返回修剪后的二叉搜索树的新根。相信看到这道题的人都认为这是一道简单的题（其实leetcode上也标注为simple）。但是真的不简单！递归方法的直接思路是：递归处理，然后遇到root->valval>high，一波修改，又快又利落。编写下面的代码并不难：returnnullptr;root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);returnroot;}};但是，[1,3]区间在二叉搜索树中并不是简单地由节点3和左子节点0来确定中心的，还要考虑节点0的右子树。我们重新关注第二个例子，如图：669.对二叉搜索树进行剪枝，所以上面的代码是不可行的！从图中可以看出，二叉树需要重构。想一想，这个问题有点复杂。其实重构并没有那么复杂。在上图中，我们发现0号节点不满足区间要求，所以直接将0号节点的右孩子2号节点赋给3号节点的左孩子就可以了（即把0号节点从二叉树），如图：669.Prunethebinarysearchtree1理解最关键的部分。我们处于递归三部曲中：确定递归函数的参数和返回值。为什么我们需要这里的返回值？因为需要遍历整棵树并进行修改，但是不需要返回值也可以，我们也可以完成剪枝的操作（其实就是去除二叉树的节点）。但是有返回值，比较方便，可以通过递归函数的返回值来移除结点。在二叉树：搜索树中的插入操作和二叉树：搜索树中的删除操作中已经了解了这种方法。代码如下：TreeNode*trimBST(TreeNode*root,intlow,inthigh)判断终止条件终止条件不做剪枝操作，所以遇到空节点返回即可。如果（root==nullptr）returnnullptr；判断单级递归的逻辑如果root（当前节点）的元素小于low的值，则对右子树进行递归，返回满足条件的右子树的头节点。代码如下：if(root->valright,low,high);//找到符合区间[low,high]的节点returnright;}如果root(currentnode)如果元素大于high，则递归左子树，返回满足条件的左子树的头节点。代码如下：if(root->val>high){TreeNode*left=trimBST(root->left,low,high);//找到符合区间[low,high]的节点returnleft;}，下一层处理左子树的结果赋值给root->left，处理右子树的结果赋值给root->right。最后回到根节点，代码如下：root->left=trimBST(root->left,low,high);//root->left访问符合条件的左孩子root->right=trimBST(root->right,low,high);//root->right访问符合条件的右孩子returnroot;这时候大家有没有发现二叉树是如何去除冗余节点的呢？回顾上面的代码，对于下图中二叉树的情况：669.对二叉搜索树1进行剪枝。下面的代码相当于将节点0的右孩子（节点2）返回给上层，if(root->valright,low,high);//找到符合区间[low,high]的节点returnright;}那么下面的代码就相当于在下一层（Node2）中使用节点3的左孩子返回节点0的右孩子。root->left=trimBST(root->left,low,high);此时节点3的右孩子成为节点2，节点0从二叉树中移除。最终整体代码如下：root->right,low,high);//找到符合范围[low,high]的节点returnright;}if(root->val>high){TreeNode*left=trimBST(root->left,low,high);//找到满足区间[low,high]的节点returnleft;}root->left=trimBST(root->left,low,high);//root->left访问符合条件的左孩子root->right=trimBST(root->right,low,high);//root->right连接到合格的右孩子returnroot;}};精简后代码如下：,low,high);if(root->val>high)returntrimBST(root->left,low,high);root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);returnroot;}};光看代码不容易看懂节点是符合去除的，这部分可以自己模拟一下！由于二叉搜索树的有序性，迭代法不需要用栈来模拟递归过程。剪枝的时候可以分为三步：将根移动到[L,R]范围内，注意左闭右闭区间pruningtheleftsubtreepruningtherightsubtree代码如下：classSolution{public:TreeNode*trimBST(TreeNode*root,intL,intR){if(!root)returnnullptr;//处理头节点，让root移动到[L,R]的范围内，注意左右closurewhile(root!=nullptr&&(root->valval>R)){if(root->valright;//小于L向右走elseroot=root->left;//大于LR往左走}TreeNode*cur=root;//此时root已经在[L,R]范围内，处理左子元素小于L的情况while(cur!=nullptr){while(cur->left&&cur->left->valleft=cur->left->right;}cur=cur->left;}cur=root;//此时root已经在[L,R]范围内，处理右孩子大于R的情况while(cur!=nullptr){while(cur->right&&cur->right->val>R){cur->right=cur->right->left;}cur=cur->right;}returnroot;}};总结二叉搜索树的剪枝并不难，但是在递归的方法中，大家可以看到我费了很大功夫来解释如何删除节点。这个想法其实很绕。最终代码非常干净。如果对递归没有深刻的理解，这道题还是有难度的！这道题我还是给出了递归的方法和迭代的方法。初学者可以掌握递归。如果您想了解更多，请编写迭代方法。其他语言版本JavaclassSolution{publicTreeNodetrimBST(TreeNoderoot,intlow,inthigh){if(root==null){returnnull;}if(root.valhigh){returntrimBST(root.left,low,high);}//根在[low,high]范围内root.left=trimBST(root.left,low,high);root.right=trimBST(root.right,low,high);returnroot;}}PythonclassSolution:deftrimBST(self,root:TreeNode,low:int,high:int)->TreeNode:ifnotroot:returnrootifroot.valhigh:returnsself.trimBST(root.left,low,high)//寻找符合区间[low,high]的节点root.left=self.trimBST(root.left,low,high)//root->左访问符合条件的左孩子root.right=self.trimBST(root.right,low,high)//root->右访问满足需求条件的右子returnroot本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。
