当前位置:首页 » 《关注互联网》 » 正文

【二叉树进阶】--- 二叉搜索树转双向链表 && 最近公共祖先

21 人参与  2024年09月08日 14:02  分类 : 《关注互联网》  评论

点击全文阅读


 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏:     算法Journey


本篇博客我们继续了解一些二叉树的进阶算法。


? 二叉搜索 树转化为双向循环链表

? 题目内容

将二叉搜索树转化为排序好的双向循环链表

 ? 题目解析

双向循环链表所连接的结点是有序的。题目要求原地转换,也就是说不允许新new结点形成新的链表,而是改变搜索树中结点指针指向。搜索树中结点的值都是唯一的,我们无需担心出现重复值结点。

? 算法原理

✏️ 思路一:

  题目要求链表中的节点是排好序的,因此结合二叉搜索树的性质(二叉搜索树中序遍历出来是有序的),我们可以按照对二叉树进行中序遍历,然后依次将节点指针存进vector里,最后遍历vector将各个节点的前驱和后继指针给处理好,最后别忘记头节点前驱指向尾节点,尾节点后继指向头节点。

动图演示:

参考代码:

class Solution {public:   void InOrder(Node* root,vector<Node*>& treev) //利用中序遍历 因为二叉搜索树中序是排好序的   {     if(root == nullptr)       return;     InOrder(root->left,treev);     treev.push_back(root); //存进数组     InOrder(root->right,treev);     }    Node* treeToDoublyList(Node* root)     {        if(root == nullptr)         return root;       vector<Node*> treev;       InOrder(root,treev);       int cur = 1 ;       Node* prev = treev[0];       Node* del = treev[1];        while(cur < treev.size()) //调整好指针指向       {             del = treev[cur];             prev->right = del;             del->left = prev;             prev = del;             cur++;       }      treev[0]->left = treev[cur-1];      treev[cur-1]->right = treev[0];         return treev[0];    }};

分析:这种思路简单,但是空间复杂度达到了O(N)(用vector存节点指针导致),是否有其他思路能优化到O(1),在遍历的同时修改指针指向呢?

✏️ 思路二:

 我们之前创建一个链表除了先提前new出节点再连接外,其实还有一个方法可以动态创建链表。

当我们中序遍历二叉搜索树时就可采取类似的做法。不同的是,我们需要记录前驱节点prev,ptail->next = node,此时的node就是我们中序遍历的当前访问节点,此时ptail需要更新成node(当前访问节点),prev就是上一个按中序被访问节点,所以我们需要在更新ptail之前记录prev,同时更新好前驱和后继指针的指向。

动画演示:

核心步骤:

       ptail->right =root;        Node* prev = ptail; //ptail其实就是前驱结点       ptail = ptail->right;        ptail->left = prev

参考代码:

  Node* phead = nullptr;   Node* ptail = nullptr;   void InOrder(Node* root) //利用中序遍历 因为二叉搜索树中序是排好序的   {     if(root == nullptr)       return;     InOrder(root->left);     if(phead == nullptr) //头结点 也就是搜索树的最左      phead = ptail = root;     else      {       ptail->right =root;        Node* prev = ptail; //ptail其实就是前驱结点       ptail = ptail->right;        ptail->left = prev;     }       InOrder(root->right);     }    Node* treeToDoublyList(Node* root)     {        if(root == nullptr)         return root;         InOrder(root);         phead->left = ptail;         ptail->right = phead;         return phead;     }

? 二叉树的最近公共祖先

? 题目内容

二叉树的最近公共祖先

? 题目解析

注意点1:一个节点也可以是它自己的祖先注意点2:要找的祖先公共要是最近也就是深度最大。

? 算法原理

✏️ 思路一:

1.题目要求我们找公共祖先,那我们首要任务是求出节点到根节点路径所经过的节点。

2.我们可以求出每个节点的祖先路径分别装进数组里。

3.求路径:我们可以设计一个递归函数,它的功能是判断子树是否存在目标节点,直到找到目标节点为止

4.找到目标节点之后,我们就可以利用两个哈希表分别遍历数组,表示他们出现过

5.最近的公共祖先一定出现在数组的后面部分,我们可以从后往前遍历祖先路径比较短的数组,发现两个映射关系都确立的就是我们要找的。

参考代码:

bool isLeft(TreeNode* node, TreeNode* del) //看是不是在子树{if (del == nullptr)return false;if (del == node) return true;return isLeft(node, del->left) || isLeft(node,del->right);}void ancestor(vector<TreeNode*>& v, TreeNode* node, TreeNode* root, unordered_map<TreeNode*, int>& ump) //装路径进数组的函数{if (root == nullptr)return;v.push_back(root); //不论是不是都说明这是target node的祖先ump[root]++;if (root == node){return;}if (isLeft(node, root->left)) //判断在左子树还是右子树{ancestor(v, node, root->left, ump);}else{ancestor(v, node, root->right, ump);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){unordered_map<TreeNode*, int> ump;unordered_map<TreeNode*, int> umq;//分别找出各自的祖先再进行比较深度if (p == root || q == root)return root;vector<TreeNode*> vp;//存的是p的祖先vector<TreeNode*> vq;//存的是q的祖先vp.push_back(root);vq.push_back(root); ump[root]++;umq[root]++;if (isLeft(p, root->left)){ancestor(vp, p, root->left, ump);//在左子树 递归进去}else{ancestor(vp, p, root->right, ump); //在右子树}if (isLeft(q, root->left)){ancestor(vq, q, root->left, umq);}else{ancestor(vq, q, root->right, umq);}//比较最近祖先vector<TreeNode*> min = vp;if (vp.size() > vq.size()){min = vq;}  TreeNode* near = nullptr;for (int i = min.size() - 1 ; i >= 0; --){if (ump[min[i]] && umq[min[i]]){near = min[i];                break;}}return near;}

这种思路比较简单,但是时间复杂度较大且调用栈空间较多,是一笔不小的开销。

✏️ 思路二:

仔细观察,我们发现思路1:仔细观察一下,两个结点,最近公共祖先的特征就是一个结点在最近公共祖先的左边,一个结点在最近公共祖先的右边。比如图一6和4的公共祖先有5和3,但是只有最近公共祖先5满足6在左边,4在右边。值得注意的是,对于图二这种情况,如果最近公共祖先是p和q其中一个,我们直接返回当前的root即可。

因此有:

我们首先需要一个函数判断结点在哪个子树,这里注意的是,我们可以假设先这个结点在左子树,如果返回false,则说明结点在右子树了,反之在左子树。也就是下方第二个参数我们传root->left即可。
 bool isleftOright(TreeNode* node,TreeNode* root)    {        if(root == nullptr)          return false;        return root == node ||isleftOright(node,root->left) ||                 isleftOright(node,root>right);      } //非空的话 如果当前节点是要找的直接返回否则在左右子树找 所以用||
若两个结点分别在一左一右,直接返回当前root即可。若两个结点都在左子树或都在右子树,此时我们需要递归进当前子树的左子树或右子树,继续寻找公共祖先。在每次确定结点在左子树还是右子树,我们需要处理特殊情况看是否当前结点就是p或q.

参考代码:

class Solution {public:    bool isleftOright(TreeNode* node,TreeNode* root)    {        if(root == nullptr)          return false;        return root == node ||isleftOright(node,root->left) ||  isleftOright(node,root->right);      }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (p == root || q == root)//最近公共祖先为p q其中一个return root;        bool pinleft = isleftOright(p,root->left);        bool pinright = !pinleft; //非左即右        bool qinleft = isleftOright(q,root->left);        bool qinright = !qinleft;        //p q分别在左右子树        if((pinleft && qinright) || (qinleft && pinright))          return root;       //p q都在左右子树        else if(pinleft && qinleft)          return lowestCommonAncestor(root->left,p,q);         else          return lowestCommonAncestor(root->right,p,q); } 
这种思路比思路一调用栈层数少了许多,但也是有一定开销的。这种思路最坏情况下时间复杂度是O(N^2).

✏️ 思路三:

   归根结底,找公共祖先也就是找公共节点,如果我们能求出两个节点的祖先路径,就能转化为链表相交问题了。问题是如何优化求路径呢?

1. 我们可以按照前序遍历的思路,找x结点的路径。

2.遇到root结点先push⼊栈,因为root就算不是x,但是root可能是根->x路径中⼀个分支结点,当这个节点左右子树都没有要找的节点的话,说明上面入栈的root不是根->x路径中⼀个分⽀结点,此时就可以pop出栈回退,继续去其他分⽀路径进行查找

3.链表相交问题我们可以先用哈希map遍历其中一条路径,再遍历另一条路径时,由于我们前序+栈得到的是从下到上的路径,所以第一次两个哈希表都有映射说明就是交点,也就是最近公共祖先。

参考代码:

    bool GetPath(TreeNode*root,TreeNode* p, stack<TreeNode*>& s)//求路径    {          if(root == nullptr)        return false;         s.push(root);        if(root == p)//找到目标节点         return true;        if(GetPath(root->left,p,s)) //左子树找 没有就去右子树        {              return true;         }        if(GetPath(root->right,p,s))        {            return true;        }        //左右子树都没有 回退        s.pop();        return false;    } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){          stack<TreeNode*> sp;        stack<TreeNode*> sq;unordered_map<TreeNode*, int> ump;unordered_map<TreeNode*, int> umq;if (p == root || q == root)return root;       //求路径GetPath(root,p,sp);GetPath(root,q,sq);       while(!sp.empty())       {            TreeNode* top = sp.top();            ump[top]++;            sp.pop();       }       TreeNode* near = nullptr;       //链表相交        while(!sq.empty())       {           TreeNode* top = sq.top();           umq[top]++;           if(umq[top] && ump[top]) //两个都有映射           {              near = top;              break;           }          sq.pop();       }      return near;} 


完(๑¯ω¯๑)


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/157035.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1