首页 > 编程语言 >代码随想录算法训练营第二十二天| 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

代码随想录算法训练营第二十二天| 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

时间:2023-08-26 12:55:38浏览次数:50  
标签:TreeNode cur val root 二叉 搜索 树中 节点 left

 

 235. 二叉搜索树的最近公共祖先 

    卡哥建议:相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。 

    题目链接/文章讲解:https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

    视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww

    做题思路:

     理解了二叉树的最近公共祖先那道题后,那这道题无非利用了二叉搜索树的特点,因为是有序树,所有 如果 中间节点是 q 和 p 的公共祖先,那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。把二叉搜索树以中序遍历的方式写成数组也好理解这点。

   所以当我们从上向下去递归遍历,第一次遇到 cur节点是数值在[p, q]区间中,那么cur就是 p和q的最近公共祖先。如下图,第一次遇到后,就不用向左或向右遍历了。

   在遍历二叉搜索树的时候就是寻找区间[p->val, q->val](注意这里是左闭右闭)。

   如果 cur->val 大于 p->val,同时 cur->val 大于q->val,那么就应该向左遍历(说明目标区间在左子树上),因为左子树比根节点小,右子树比根节点大,如果cur值此时都大于区间 [p,q],说明不在右子树那边,所以要向左遍历。需要注意的是此时不知道p和q谁大,所以两个都要判断;

   如果 cur->val 小于 p->val,同时 cur->val 小于 q->val,那么就应该向右遍历(目标区间在右子树),原因同理。

剩下的情况,就是cur节点在区间(p->val <= cur->val && cur->val <= q->val)或者 (q->val <= cur->val && cur->val <= p->val)中,那么cur就是最近公共祖先了,直接返回cur。

    本题代码:

 1 class Solution {
 2 private:
 3     TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
 4         if (cur == NULL) return cur;
 5                                                         // 中
 6         if (cur->val > p->val && cur->val > q->val) {   // 左
 7             TreeNode* left = traversal(cur->left, p, q);
 8             if (left != NULL) {
 9                 return left;
10             }
11         }
12 
13         if (cur->val < p->val && cur->val < q->val) {   // 右
14             TreeNode* right = traversal(cur->right, p, q);
15             if (right != NULL) {
16                 return right;
17             }
18         }
19         return cur;//else 的情况
20     }
21 public:
22     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
23         return traversal(root, p, q);
24     }
25 };

 

701.二叉搜索树中的插入操作  

     卡哥建议:本题比想象中的简单,大家可以先自己想一想应该怎么做,然后看视频讲解,就发现 本题为什么比较简单了。

    题目链接/文章讲解:https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html

    视频讲解:https://www.bilibili.com/video/BV1Et4y1c78Y

     做题思路:

     这里看卡哥视频理解的思路更清晰。

   只要按照二叉搜索树的规则去遍历,遇到空节点就插入节点就可以了。

   搜索树是有方向了,可以根据插入元素的数值,决定递归方向。

     本题代码:

 1 class Solution {
 2 public:
 3     TreeNode* insertIntoBST(TreeNode* root, int val) {
 4         if (root == NULL) {
 5             TreeNode* node = new TreeNode(val);
 6             return node;
 7         }
 8         if (root->val > val) root->left = insertIntoBST(root->left, val);//插入新节点的值小于根节点的值,就向左遍历
 9         if (root->val < val) root->right = insertIntoBST(root->right, val);
10         return root;
11     }
12 };

 

450.删除二叉搜索树中的节点  

     卡哥建议:相对于 插入操作,本题就有难度了,涉及到改树的结构 

    题目链接/文章讲解:https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

    视频讲解:https://www.bilibili.com/video/BV1tP41177us

    做题思路:

    二叉搜索树中删除节点遇到的情况都搞清楚。

    有以下五种情况:

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
    • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点,这里画个图就能理解。
    • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
    • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
      第五种情况有点难以理解,看下面动画:

 

     本题代码:

 1 class Solution {
 2 public:
 3     TreeNode* deleteNode(TreeNode* root, int key) {
 4         if (root == nullptr) return root; // 第一种情况:没找到删除的节点,遍历到空节点直接返回了
 5         if (root->val == key) {
 6             // 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
 7             if (root->left == nullptr && root->right == nullptr) {
 8                 ///! 内存释放
 9                 delete root;
10                 return nullptr;
11             }
12             // 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点
13             else if (root->left == nullptr) {
14                 auto retNode = root->right;
15                 ///! 内存释放
16                 delete root;
17                 return retNode;
18             }
19             // 第四种情况:其右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
20             else if (root->right == nullptr) {
21                 auto retNode = root->left;
22                 ///! 内存释放
23                 delete root;
24                 return retNode;
25             }
26             // 第五种情况:左右孩子节点都不为空,则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
27             // 并返回删除节点右孩子为新的根节点。
28             else {
29                 TreeNode* cur = root->right; // 找右子树最左面的节点
30                 while(cur->left != nullptr) {
31                     cur = cur->left;
32                 }
33                 cur->left = root->left; // 把要删除的节点(root)左子树放在cur的左孩子的位置
34                 TreeNode* tmp = root;   // 把root节点保存一下,下面来删除
35                 root = root->right;     // 返回旧root的右孩子作为新root
36                 delete tmp;             // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)
37                 return root;
38             }
39         }
40         if (root->val > key) root->left = deleteNode(root->left, key);//这里相当于把新的节点返回给上一层,上一层就要用 root->left 或者 root->right接住,
41         if (root->val < key) root->right = deleteNode(root->right, key);
42         return root;
43     }
44 };

 

标签:TreeNode,cur,val,root,二叉,搜索,树中,节点,left
From: https://www.cnblogs.com/romantichuaner/p/17646620.html

相关文章

  • [刷题记录Day14]Leetcode二叉树
    No.1题目前序遍历思路递归法代码publicvoidTraverse(TreeNodenode,List<Integer>list){if(node==null)return;list.add(node.val);//中Traverse(node.left,list);//左Traverse(node.right,list);//右}p......
  • [刷题记录Day15]Leetcode二叉树
    No.1题目二叉树的层序遍历思路使用队列关键点:1.每进入一层,层内的节点都被处理完成2.开始遍历层内的节点前,必须先记录该层的节点数量,不能访问到下一层的节点代码publicList<List<Integer>>levelOrder(TreeNoderoot){Queue<TreeNode>queue=newLinkedList......
  • [刷题记录Day17]Leetcode二叉树
    No.1题目平衡二叉树思路递归法在遍历中比较左右子树的高度差递归分析参数:当前传入节点。返回值:以当前传入节点为根节点的树的高度那么如何标记左右子树是否差值大于1呢?可以返回-1来标记已经不符合平衡树的规则了明确终止条件:递归的过程中依然是遇到空节点了为终止,返......
  • [刷题记录Day16]Leetcode二叉树
    No.1题目二叉树的最大深度思路递归其实是后序遍历的方式代码publicintmaxDepth(TreeNoderoot){if(root==null)return0;returnMath.max(1+maxDepth(root.left),1+maxDepth(root.right));}No.2题目二叉树的最小深度思路......
  • [刷题记录Day18]Leetcode二叉树
    No.1题目找树左下角的值思路队列,层序遍历Deque既可以用作栈也可以用作队列,谨慎使用代码publicintfindBottomLeftValue(TreeNoderoot){Queue<TreeNode>queue=newLinkedList<>();queue.add(root);intresult=0;//记录最后一行第一个元素......
  • 《算法笔记》树与二叉树专题练习
    1、复原二叉树(由前序和中序求后序)题目描述小明在做数据结构的作业,其中一题是给你一棵二叉树的前序遍历和中序遍历结果,要求你写出这棵二叉树的后序遍历结果。输入输入包含多组测试数据。每组输入包含两个字符串,分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写......
  • 二叉搜索树的公共祖先
    力扣(LeetCode)官网-全球极客挚爱的技术成长平台1TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){2if(root==nullptr||root==p||root==q)returnroot;3//如果该结点比两个结点都大或则都小,则只需要搜索右子树或左子树,而......
  • 力扣---1448. 统计二叉树中好节点的数目
    给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。「好节点」X定义为:从根到该节点X所经过的节点中,没有任何节点的值大于X的值。 示例1:输入:root=[3,1,4,3,null,1,5]输出:4解释:图中蓝色节点为好节点。根节点(3)永远是个好节点。节点4->(3,4)是路......
  • 「学习笔记」meet in the middle(折半搜索)
    meetinthemiddle,适用于输入数据较小,但也没小到可以直接用暴力搜索通过的情况。主要的思想就是讲整个搜索过程分成两半进行,最后在将这两半的结果进行合并,对于搜索复杂度为\(O(a^b)\)的情况,meetinthemiddle可以将它优化为\(O(a^{\frac{b}{2}})\)。题目P5691[NOI2001]......
  • 二叉树的最近公共祖先
    235.二叉搜索树的最近公共祖先-力扣(LeetCode)经验1:在二叉树中找满足条件的结点的问题一般使用后续遍历,也就是说如果找到了这个结点那么就将它返回给上层,然后层层返回最终返回到根结点经验2:本题的解题技巧:如果在某一结点找到了p或q,那么就不用往下递归了,直接将这个结点返回,即便......