一.二叉樹的最近公共祖先

鏈接

二叉樹的最近公共祖先

題目再現(xiàn)

?『Ⅰ』思路一：轉(zhuǎn)換成相交鏈表問題

?觀察上圖，節(jié)點1和節(jié)點4的最近公共祖先是3，這是不是很像相交鏈表的問題，關(guān)于相交鏈表，曾經(jīng)我在另一篇文章里寫到過，讀者可以參考：反轉(zhuǎn)鏈表 合并鏈表 相交鏈表

但是要轉(zhuǎn)換成相交鏈表，就要從后向前遍歷，如果節(jié)點中還存在一個指針，指向父節(jié)點就好了，這種結(jié)構(gòu)其實叫三叉鏈結(jié)構(gòu)：

?但是這題給我們的只是一個普通的二叉樹，沒有三叉鏈，那該怎么辦呢？

那么就轉(zhuǎn)換為第二種思路：尋找節(jié)點的祖先路徑

『Ⅱ』思路二：尋找節(jié)點的祖先路徑

? 我們可以把要找的兩個節(jié)點的路徑找出來，然后存到棧里，這樣把兩個節(jié)點的祖先路徑找出來后，就可以轉(zhuǎn)換成鏈表相交問題了。

關(guān)于該怎么入棧：

我們先讓節(jié)點入棧，然后判斷它是否等于我們要找的節(jié)點，如果是，則返回true；如果不是，則

? ? ? ? ? ? ? ? 1.如果左節(jié)點不為空，返回true；

? ? ? ? ? ? ? ? 2.如果右節(jié)點不為空，返回true；

? ? ? ? ? ? ? ? 3.如果左右節(jié)點都為空，則pop掉棧頂?shù)脑?#xff0c;返回false；

完整代碼：

class Solution {
public:bool findpath(TreeNode*cur,TreeNode*x,stack<TreeNode*>&path)  //注意這里要傳引用{if(cur==nullptr)return false;path.push(cur);if(cur==x)return true;if(findpath(cur->left,x,path))return true;if(findpath(cur->right,x,path))return true;path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath;stack<TreeNode*> qpath;findpath(root,p,ppath);findpath(root,q,qpath);while(ppath.size()>qpath.size())  //使兩個棧一樣長{ppath.pop();}while(ppath.size()<qpath.size()){qpath.pop();}while(ppath.top()!=qpath.top())   //從棧頂開始，尋找第一個相同的數(shù)據(jù){ppath.pop();qpath.pop();}return ppath.top();}
};

? ? ? ? ?

可以看到，這種方法效率使非常高的，它的時間復(fù)雜度是O（N）;

?『Ⅲ』思路三：暴力查找

其實當(dāng)兩個節(jié)點分別在左樹和右樹時，它們最近的公共祖先就是根節(jié)點，如果不在樹兩邊，而是都在左樹，或是都在右樹，那么就可以轉(zhuǎn)化成子問題，遞歸解決。

如下圖：

?注意，如果有一個節(jié)點恰好是根節(jié)點，那么這個節(jié)點就是最近的公共祖先，也是說一個節(jié)點的祖先也算它自己。

如下圖：

?那么該怎么判斷節(jié)點是在左樹還是右樹呢?

我們可以定義四個布爾變量，分別是：pinleft（p在左樹）? ?pinright（p在右樹）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?qinleft （q在左樹 ） qinright（q在右樹）

哪個布爾值為真就表明這個節(jié)點在哪邊。

完整代碼：

class Solution {
public:bool find(TreeNode*cur,TreeNode*x){if(cur==nullptr)return false;return cur==x||find(cur->left,x)||find(cur->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode*q)  {if(root==nullptr)return nullptr;if(root==p||root==q)  //某一個節(jié)點為根return root;bool pinleft,pinright;bool qinleft,qinright;pinleft=find(root->left,p);   //去左樹尋找p節(jié)點pinright=!pinleft;qinleft=find(root->left,q);   //去左樹尋找q節(jié)點qinright=!qinleft;if(pinleft&&qinleft)   //都在左樹轉(zhuǎn)化成子問題return lowestCommonAncestor(root->left,p,q);else if(pinright&&qinright)    //都在右樹轉(zhuǎn)化成子問題return lowestCommonAncestor(root->right,p,q);else    //分別在左樹和右樹return root;}
};

可以看到，這個算法的效率是很差的，它的時間復(fù)雜度是O（N^2）。

---

二.二叉搜索樹轉(zhuǎn)換成排好序的雙向鏈表?

鏈接

二叉搜索樹轉(zhuǎn)換成排好序的雙向鏈表

題目再現(xiàn)

?解法

根據(jù)題意，原二叉搜索樹的左指針就是雙鏈表的前驅(qū)指針，右指針就是雙鏈表的后繼指針；

而且本題還要求空間復(fù)雜度是O（1），也就是說不能額外開空間，其實要是能額外開空間，那么這題就非常簡單了。

我們知道，二叉搜索樹的中序遍歷結(jié)果是升序列，這恰好滿足了題目排好序的要求；

那要怎么在原樹上操作，使它轉(zhuǎn)換成雙鏈表呢？

舉個例子：

對于我們過去（prev）的事，現(xiàn)在（cur）的我們肯定是一清二楚的，而且是可以確定的，但未來（next）的事并不能確定；

但如果我們是從未來穿越回現(xiàn)在的，那么穿越回來的我們，就可以確定未來的事。所以說過去（prev）的未來（next）就是現(xiàn)在（cur）。

回到題目，所以cur的左指針（left）就是雙鏈表的前驅(qū)（prev），prev的右指針就是后繼（next），然后再更新一下prev即可。

完整代碼：

class Solution {
public:void InOrder(TreeNode*cur,TreeNode*&prev)   //注意要傳引用{if(cur==nullptr)return;InOrder(cur->left,prev);cur->left=prev;   //cur的左指針就是previf(prev)   //注意判斷prev是否為空prev->right=cur;   //prev的右指針就是curprev=cur;  //更新prevInOrder(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree==nullptr)return nullptr;TreeNode*prev=nullptr;   //定義一個前驅(qū)指針I(yè)nOrder(pRootOfTree,prev);   //中序遍歷TreeNode*head=pRootOfTree;while(head->left)   //最左邊的節(jié)點即為雙鏈表的頭{head=head->left;}return head;}
};

---

三.根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹

鏈接

根據(jù)一棵樹的前序序列與中序序列構(gòu)建二叉樹

題目再現(xiàn)

?解法

眾所周知，前序遍歷的順序為：根? 左? 右

? ? ? ? ? ? ? ? ? 中序遍歷的順序為：左? 根? 右

所以根據(jù)前序序列就可以確定根，確定了根后就可以分成左子樹和右子樹；

確定好根后，根據(jù)中序序列就可以分割左子樹和右子樹的區(qū)間，然后構(gòu)建樹；

而左子樹或是右子樹也有根，這樣就可以轉(zhuǎn)化成子問題，遞歸實現(xiàn)，但要注意，前序序列中的每個數(shù)只能使用一次。

?完整代碼：

class Solution {
public://注意這個prei用于遍歷前序序列數(shù)組，因為每個數(shù)只能用一次，所以要傳引用TreeNode*_build(vector<int>& preorder, vector<int>& inorder,int &prei,int inbegin,int inend){if(inbegin>inend)   //當(dāng)區(qū)間不存在時返回空指針return nullptr;TreeNode*preroot=new TreeNode(preorder[prei]);int rooti=inbegin;     //找根在中序序列中的位置while(rooti<=inend){if(preorder[prei]==inorder[rooti])   //找到后跳出循環(huán)break;rooti++;}prei++;   //本次確定好根后，prei++找下一個根//分割區(qū)間，遞歸構(gòu)建//[inbegin,rooti-1] rooti [rooti+1,inend]preroot->left=_build(preorder,inorder,prei,inbegin,rooti-1);preroot->right=_build(preorder,inorder,prei,rooti+1,inend);return preroot;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return _build(preorder,inorder,i,0,inorder.size()-1);}
};

---

🐬🤖本篇文章到此就結(jié)束了，?若有錯誤或是建議的話，歡迎小伙伴們指出；🕊?👻

😄😆希望小伙伴們能支持支持博主啊，你們的支持對我很重要哦；🥰🤩

😍😁謝謝你的閱讀。😸😼