祝大家新年快樂(lè)呀，雖這段時(shí)間正值過(guò)年，但是我們不要忘記停下學(xué)習(xí)的腳步。今天我們一起看一到力扣上的經(jīng)典二叉樹(shù)OJ題，求二叉樹(shù)兩個(gè)結(jié)點(diǎn)最近的公共祖先。
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
鏈接給大家放在這里啦，大家一點(diǎn)即達(dá)
首先我們看到題目，這道題并沒(méi)有告訴我們這是一棵怎么樣的二叉樹(shù)，不是完全二叉，也不是搜索二叉，所以這道題做起來(lái)就比較棘手，完全二叉樹(shù)的話我們可以根據(jù)結(jié)點(diǎn)的編號(hào)查找，搜索二叉我們也可以按照大小確定范圍，但是眼前這顆數(shù)完全是一個(gè)亂序的，所以這道題怎么下手呢？
方法一? ? ? ??
我們不妨先確定要查找的兩個(gè)結(jié)點(diǎn)在根結(jié)點(diǎn)的哪邊，我們拿5和8舉例子
很明顯。這兩個(gè)結(jié)點(diǎn)一個(gè)在根結(jié)點(diǎn)的左邊，一個(gè)在右邊，所以他們最近公共結(jié)點(diǎn)肯定就是根節(jié)點(diǎn)。
那如果在同一邊呢？比如6和4，
結(jié)點(diǎn)6和4都在根節(jié)點(diǎn)的左子樹(shù)上，我們可以用剛才的方法，遞歸根節(jié)點(diǎn)的左子樹(shù)，以結(jié)點(diǎn)5為跟，就可以求出他們最近的公共結(jié)點(diǎn)為5；思路有了，現(xiàn)在我們編寫(xiě)代碼
我們先封裝一個(gè)函數(shù)判斷結(jié)點(diǎn)是否在這個(gè)以root為根結(jié)點(diǎn)的二叉樹(shù)內(nèi)：
bool IsTree(TreeNode*root,TreeNode* x)
{
if(root==nullptr)
{
return false;
}
return root==x||IsTree(root->left,x)||IsTree(root->right,x);
}然后我們?cè)诮o定的函數(shù)內(nèi)實(shí)現(xiàn)出這個(gè)函數(shù)。
這里教大家一個(gè)簡(jiǎn)便的方法。我們定義幾個(gè)bool變量：
bool Leftp,Rightp,Leftq,Rightq;//依次代表的含義是p在左子樹(shù)，P在右子樹(shù)，q在左子樹(shù)，q在右子樹(shù)然后我們?nèi)フ襭在root的那一邊，把返回值給Leftp,讓Rightp=!Left;
Leftp=IsTree(root->left,p);
Rightp=!Leftp;這樣寫(xiě)大家能理解什么意思嗎？在root的左子樹(shù)去找結(jié)點(diǎn)p的結(jié)果賦給Leftp,不管是不是在左邊，右邊的結(jié)果肯定就是！Leftp,假如Leftp是true，那Rightp就是false;如果Leftp是false,那Rightp就是true;二者肯定一真一假，判斷q結(jié)點(diǎn)在哪邊也是如此
Leftq=IsTree(root->left,q);
Rightq=!Leftq;然后我們判斷如果兩個(gè)結(jié)點(diǎn)pq有一個(gè)是根節(jié)點(diǎn)root的話，那就返回root就可以了
if(p==root||q==root)
{
return root;
}其次，判斷，如果pq一個(gè)在根節(jié)點(diǎn)左邊，一個(gè)在右邊，那還是返回根節(jié)點(diǎn)。即
if((Leftp&&Rightq)||(Rightp&&Leftq))//中間用||連接是因?yàn)槲覀円膊恢浪麄冊(cè)谀倪?，反正肯定有一組是真的
{
return root;
}然后再判斷他們?cè)谕贿叺那闆r,代碼運(yùn)行到這里，肯定能證明他們不在同一邊，我們先判斷同時(shí)在左子樹(shù)的情況：
else if(Leftp&&Leftq)
{
return lowestCommonAncestor(root->left,p,q);
}剩下的就是同時(shí)在右子樹(shù)的情況：
else{
return lowestCommonAncestor(root->right,p,q);
}然后我們提交，就可以看到通過(guò)啦。但是我們思考一下，這樣的寫(xiě)法時(shí)間復(fù)雜度是很大的。如果這棵樹(shù)是一個(gè)類(lèi)似于單邊的二叉樹(shù)，也就是另外一邊的結(jié)點(diǎn)個(gè)數(shù)很少很少，幾乎全部集中在一邊，且要找的兩個(gè)結(jié)點(diǎn)都在最后，即：
我們要查找的兩個(gè)結(jié)點(diǎn)在這個(gè)位置，它的時(shí)間復(fù)雜度是多少？可以看到，我們以3為根結(jié)點(diǎn)查詢(xún)1和3在哪邊需要走N-2次+N-3次，然后遞歸以10為根節(jié)點(diǎn)查找，再遞歸以8為根節(jié)點(diǎn)查找.......時(shí)間復(fù)雜度其實(shí)是O(N^2)的。
bool IsTree(TreeNode*root,TreeNode* x)
{
if(root==nullptr)
{
return false;
}
return root==x||IsTree(root->left,x)||IsTree(root->right,x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
bool Leftp,Rightp,Leftq,Rightq;
Leftp=IsTree(root->left,p);
Rightp=!Leftp;
Leftq=IsTree(root->left,q);
Rightq=!Leftq;
if(p==root||q==root)
{
return root;
}
if((Leftp&&Rightq)||(Rightp&&Leftq))
{
return root;
}
else if(Leftp&&Leftq)
{
return lowestCommonAncestor(root->left,p,q);
}
else{
return lowestCommonAncestor(root->right,p,q);
}
}方法二
下面我們介紹第二種方法
第二種方式是我們記錄兩個(gè)結(jié)點(diǎn)的路徑，即從根結(jié)點(diǎn)到找到他們之間所有的結(jié)點(diǎn)。例如：
結(jié)點(diǎn)6的路徑是3->5->6,結(jié)點(diǎn)4的路徑是3->5->2->4,把他們都放在兩個(gè)棧里面，比較棧的特點(diǎn)是后進(jìn)先出，然后比較這個(gè)兩個(gè)棧的第一個(gè)相同的棧頂元素。這樣的話我們最壞無(wú)非就是遍歷2次這棵樹(shù)就可以，定義兩個(gè)棧，算是以空間換時(shí)間。下面我們開(kāi)始實(shí)現(xiàn)
我們首先需要在原函數(shù)定義兩個(gè)棧，一個(gè)用于存放p結(jié)點(diǎn)的路徑，一個(gè)存放q結(jié)點(diǎn)的路徑
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> ppath;
stack<TreeNode*>qpath;
}然后我們需要封裝一個(gè)函數(shù)用來(lái)求結(jié)點(diǎn)走過(guò)的路徑Getpath();參數(shù)需要根節(jié)點(diǎn)，待求結(jié)點(diǎn),棧，即
bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)//傳引用是為了我們?cè)谡{(diào)用這個(gè)函數(shù)時(shí)對(duì)這個(gè)棧的修改可以隨時(shí)生效，不需要再拷貝用bool類(lèi)型是為了我們找到這個(gè)結(jié)點(diǎn)時(shí)就直接返回不再往下走。
下面我們實(shí)現(xiàn)這個(gè)函數(shù)，首先判斷根節(jié)點(diǎn)為空，那就返回false，接下來(lái)先把根節(jié)點(diǎn)入棧，然后判斷根結(jié)點(diǎn)是要求的路徑的結(jié)點(diǎn)，是的話返回true；
bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
if (root == nullptr)
{
return false;
}
path.push(root);
if (root == x)
{
return true;
}
}代碼走到這里，那就證明根結(jié)點(diǎn)不是x，我們遞歸左子樹(shù)，如果左子樹(shù)為真，返回true;左子樹(shù)遇到空結(jié)點(diǎn)返回false,下來(lái)遞歸右子樹(shù)，右子樹(shù)也是如此；
if (Getpath(root->left, x, path))
return true;
if (Getpath(root->right, x, path))
return true;代碼走到這里，證明根節(jié)點(diǎn)及它的左右孩子結(jié)點(diǎn)都不是x，我們需要把這個(gè)根節(jié)點(diǎn)出棧的，比如：
比如我們求結(jié)點(diǎn)4的路徑，代碼運(yùn)行到查找5的左孩子時(shí)，6先進(jìn)棧，然后遞歸6的左右子樹(shù)，都為空，已經(jīng)把6的左右子樹(shù)都查找完畢，所以4的路徑不經(jīng)過(guò)結(jié)點(diǎn)6，那這個(gè)時(shí)候需要讓6出棧，然后返回false,返回上一層遞歸。
if (root != x)
{
path.pop();
}
return false;這個(gè)函數(shù)就封裝完成。
下面寫(xiě)原函數(shù)，原函數(shù)我們首先要定義兩個(gè)棧，上面已經(jīng)定義過(guò)，這個(gè)是我們先走一遍p的路徑，再走一遍q的路徑，這個(gè)時(shí)候ppath和qpath兩個(gè)棧里面存放著p和q的路徑，我們需要讓這兩個(gè)棧的大小相等，因?yàn)閺母?jié)點(diǎn)到最近公共祖先肯定是完全一樣的，這樣才能找出公共路徑。
while (ppath.size() != qpath.size())
{
if (ppath.size() > qpath.size())
ppath.pop();
else
qpath.pop();
}這個(gè)時(shí)候兩棧存放的數(shù)據(jù)個(gè)數(shù)相等，只需比較棧頂元素是否相等，不相等再同時(shí)出棧，相等時(shí)返回棧頂元素就可以啦。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-829764.html
while (ppath.top() != qpath.top())
{
ppath.pop();
qpath.pop();
}
return ppath.top();這樣代碼就能提交過(guò)啦。時(shí)間復(fù)雜度也很樂(lè)觀。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-829764.html
bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
if (root == nullptr)
{
return false;
}
path.push(root);
if (root == x)
{
return true;
}
if (Getpath(root->left, x, path))
return true;;
if (Getpath(root->right, x, path))
return true;
if (root != x)
{
path.pop();
}
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> ppath;
stack<TreeNode*>qpath;
Getpath(root, p, ppath);
Getpath(root, q, qpath);
while (ppath.size() != qpath.size())
{
if (ppath.size() > qpath.size())
ppath.pop();
else
qpath.pop();
}
while (ppath.top() != qpath.top())
{
ppath.pop();
qpath.pop();
}
return ppath.top();
}到了這里，關(guān)于力扣236——二叉樹(shù)的最近公共祖先的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
