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); } //非空的话 如果当前节点是要找的直接返回否则在左右子树找 所以用||参考代码：
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); } 
✏️ 思路三：
归根结底，找公共祖先也就是找公共节点，如果我们能求出两个节点的祖先路径，就能转化为链表相交问题了。问题是如何优化求路径呢？
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;}
完(๑¯ω¯๑)