Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏： 数据结构
本篇博客我们继续了解一些二叉树的进阶算法。
🏠 二叉搜索 树转化为双向循环链表
📌 题目内容
将二叉搜索树转化为排序好的双向循环链表
📌 题目解析
- 双向循环链表所连接的结点是有序的。
- 题目要求原地转换，也就是说不允许新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);elsereturn 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;} 完(๑¯ω¯๑)
