修剪一棵二叉搜索树，你会吗？

如果不对递归有深刻的理解，本题有点难。单纯移除一个节点那还不够，要修剪!

10年积累的成都网站设计、做网站、成都外贸网站建设公司经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有大峪免费网站建设让你可以放心的选择与我们合作。

修剪二叉搜索树

力扣链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/

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

思路

相信看到这道题目大家都感觉是一道简单题(事实上leetcode上也标明是简单)。

但还真的不简单!

递归法

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

不难写出如下代码：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr || root->val < low || root->val > high) return nullptr; 
    5. 
  
  
  
  
  5.         root->left = trimBST(root->left, low, high); 
    6. 
  
  
  
  
  6.         root->right = trimBST(root->right, low, high); 
    7. 
  
  
  
  
  7.         return root; 
    8. 
  
  
  
  
  8.     } 
    9. 
  
  
  
  
  9. }; 
    10.

然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树。

我们在重新关注一下第二个示例，如图：

669.修剪二叉搜索树

所以以上的代码是不可行的!

从图中可以看出需要重构二叉树，想想是不是本题就有点复杂了。

其实不用重构那么复杂。

在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了(就是把节点0从二叉树中移除)，如图：

669.修剪二叉搜索树1

理解了最关键部分了我们在递归三部曲：

  • 确定递归函数的参数以及返回值

这里我们为什么需要返回值呢?

因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪(其实就是从二叉树中移除节点)的操作。

但是有返回值，更方便，可以通过递归函数的返回值来移除节点。

这样的做法在二叉树：搜索树中的插入操作和二叉树：搜索树中的删除操作中大家已经了解过了。

代码如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* trimBST(TreeNode* root, int low, int high) 
    2.
  • 确定终止条件

修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了。

 
 
 
 
    
  
  
  
  
  1. if (root == nullptr ) return nullptr; 
    2.
  • 确定单层递归的逻辑

如果root(当前节点)的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

代码如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val < low) { 
    2. 
  
  
  
  
  2.     TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点 
    3. 
  
  
  
  
  3.     return right; 
    4. 
  
  
  
  
  4. } 
    5.

如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

代码如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val > high) { 
    2. 
  
  
  
  
  2.     TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点 
    3. 
  
  
  
  
  3.     return left; 
    4. 
  
  
  
  
  4. } 
    5.

接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。

最后返回root节点，代码如下：

 
 
 
 
    
  
  
  
  
  1. root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子 
    2. 
  
  
  
  
  2. root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子 
    3. 
  
  
  
  
  3. return root; 
    4.

此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢?

在回顾一下上面的代码，针对下图中二叉树的情况：

669.修剪二叉搜索树1

如下代码相当于把节点0的右孩子(节点2)返回给上一层，

 
 
 
 
    
  
  
  
  
  1. if (root->val < low) { 
    2. 
  
  
  
  
  2.     TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点 
    3. 
  
  
  
  
  3.     return right; 
    4. 
  
  
  
  
  4. } 
    5.

然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子(节点2) 接住。

 
 
 
 
    
  
  
  
  
  1. root->left = trimBST(root->left, low, high); 
    2.

此时节点3的右孩子就变成了节点2，将节点0从二叉树中移除了。

最后整体代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr ) return nullptr; 
    5. 
  
  
  
  
  5.         if (root->val < low) { 
    6. 
  
  
  
  
  6.             TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点 
    7. 
  
  
  
  
  7.             return right; 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.         if (root->val > high) { 
    10. 
  
  
  
  
  10.             TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点 
    11. 
  
  
  
  
  11.             return left; 
    12. 
  
  
  
  
  12.         } 
    13. 
  
  
  
  
  13.         root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子 
    14. 
  
  
  
  
  14.         root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子 
    15. 
  
  
  
  
  15.         return root; 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17. }; 
    18.

精简之后代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr) return nullptr; 
    5. 
  
  
  
  
  5.         if (root->val < low) return trimBST(root->right, low, high); 
    6. 
  
  
  
  
  6.         if (root->val > high) return trimBST(root->left, low, high); 
    7. 
  
  
  
  
  7.         root->left = trimBST(root->left, low, high); 
    8. 
  
  
  
  
  8.         root->right = trimBST(root->right, low, high); 
    9. 
  
  
  
  
  9.         return root; 
    10. 
  
  
  
  
  10.     } 
    11. 
  
  
  
  
  11. }; 
    12.

只看代码，其实不太好理解节点是符合移除的，这一块大家可以自己在模拟模拟!

迭代法

因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。

在剪枝的时候，可以分为三步：

  • 将root移动到[L, R] 范围内，注意是左闭右闭区间
  • 剪枝左子树
  • 剪枝右子树

代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int L, int R) { 
    4. 
  
  
  
  
  4.         if (!root) return nullptr; 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.         // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭 
    7. 
  
  
  
  
  7.         while (root != nullptr && (root->val < L || root->val > R)) { 
    8. 
  
  
  
  
  8.             if (root->val < L) root = root->right; // 小于L往右走 
    9. 
  
  
  
  
  9.             else root = root->left; // 大于R往左走 
    10. 
  
  
  
  
  10.         } 
    11. 
  
  
  
  
  11.         TreeNode *cur = root; 
    12. 
  
  
  
  
  12.         // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况 
    13. 
  
  
  
  
  13.         while (cur != nullptr) { 
    14. 
  
  
  
  
  14.             while (cur->left && cur->left->val < L) { 
    15. 
  
  
  
  
  15.                 cur->left = cur->left->right; 
    16. 
  
  
  
  
  16.             } 
    17. 
  
  
  
  
  17.             cur = cur->left; 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19.         cur = root; 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21.         // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况 
    22. 
  
  
  
  
  22.         while (cur != nullptr) { 
    23. 
  
  
  
  
  23.             while (cur->right && cur->right->val > R) { 
    24. 
  
  
  
  
  24.                 cur->right = cur->right->left; 
    25. 
  
  
  
  
  25.             } 
    26. 
  
  
  
  
  26.             cur = cur->right; 
    27. 
  
  
  
  
  27.         } 
    28. 
  
  
  
  
  28.         return root; 
    29. 
  
  
  
  
  29.     } 
    30. 
  
  
  
  
  30. }; 
    31.

总结

修剪二叉搜索树其实并不难，但在递归法中大家可看出我费了很大的功夫来讲解如何删除节点的，这个思路其实是比较绕的。

最终的代码倒是很简洁。

如果不对递归有深刻的理解，这道题目还是有难度的!

本题我依然给出递归法和迭代法，初学者掌握递归就可以了，如果想进一步学习，就把迭代法也写一写。

其他语言版本

Java

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public TreeNode trimBST(TreeNode root, int low, int high) { 
    3. 
  
  
  
  
  3.         if (root == null) { 
    4. 
  
  
  
  
  4.             return null; 
    5. 
  
  
  
  
  5.         } 
    6. 
  
  
  
  
  6.         if (root.val < low) { 
    7. 
  
  
  
  
  7.             return trimBST(root.right, low, high); 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.         if (root.val > high) { 
    10. 
  
  
  
  
  10.             return trimBST(root.left, low, high); 
    11. 
  
  
  
  
  11.         } 
    12. 
  
  
  
  
  12.         // root在[low,high]范围内 
    13. 
  
  
  
  
  13.         root.left = trimBST(root.left, low, high); 
    14. 
  
  
  
  
  14.         root.right = trimBST(root.right, low, high); 
    15. 
  
  
  
  
  15.         return root; 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17. } 
    18.

Python

 
 
 
 
    
  
  
  
  
  1. class Solution: 
    2. 
  
  
  
  
  2.     def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode: 
    3. 
  
  
  
  
  3.         if not root: return root 
    4. 
  
  
  
  
  4.         if root.val < low: 
    5. 
  
  
  
  
  5.             return self.trimBST(root.right,low,high)  // 寻找符合区间[low, high]的节点 
    6. 
  
  
  
  
  6.         if root.val > high: 
    7. 
  
  
  
  
  7.             return self.trimBST(root.left,low,high)  // 寻找符合区间[low, high]的节点 
    8. 
  
  
  
  
  8.         root.left = self.trimBST(root.left,low,high)  // root->left接入符合条件的左孩子 
    9. 
  
  
  
  
  9.         root.right = self.trimBST(root.right,low,high)   // root->right接入符合条件的右孩子 
    10. 
  
  
  
  
  10.         return root 
    11.

本文转载自微信公众号「代码随想录」，可以通过以下二维码关注。转载本文请联系代码随想录公众号。

网站标题：修剪一棵二叉搜索树，你会吗？
转载注明：http://www.shufengxianlan.com/qtweb/news49/129449.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

软件开发知识

行业网站建设

成都网站建设公司　　 　微信小程序开发　　 　德阳电信服务器托管　　 　成都富士康招工　　 　南充主机托管　　 　自适应网站设计　　 　成都seo优化　　 　发光字制作　　 　成都网站推广　　 　成都网站设计　　 　成都封阳台　　 　成都主机租用　　 　四川胜锦安防　　 　宜宾做网站　　 　南京护栏钻孔机　　 　成都app开发　　 　网站建设开发　　 　眉山做网站　　 　混凝土密封固化剂　　 　域名ssl证书