文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

修剪一棵二叉搜索树,你会吗?

2024-12-14 00:15

关注

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

修剪二叉搜索树

力扣链接: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. public
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
  4.         if (root == nullptr || root->val < low || root->val > high) return nullptr; 
  5.         root->left = trimBST(root->left, low, high); 
  6.         root->right = trimBST(root->right, low, high); 
  7.         return root; 
  8.     } 
  9. }; 

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

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

669.修剪二叉搜索树

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

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

其实不用重构那么复杂。

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

669.修剪二叉搜索树1

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

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

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

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

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

代码如下:

  1. TreeNode* trimBST(TreeNode* root, int low, int high) 

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

  1. if (root == nullptr ) return nullptr; 

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

代码如下:

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

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

代码如下:

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

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

最后返回root节点,代码如下:

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

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

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

669.修剪二叉搜索树1

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

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

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

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

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

最后整体代码如下:

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

精简之后代码如下:

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

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

迭代法

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

在剪枝的时候,可以分为三步:

代码如下:

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

总结

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

最终的代码倒是很简洁。

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

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

其他语言版本

Java

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

Python

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

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

 

来源:代码随想录内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯