前言：

二叉樹刷題是有固定思維的，請移步

README】二叉樹刷題框架

文章目錄

• 前言：
• 二叉樹的最近公共祖先
• 思路一
• • 思路
  • 代碼
• 思路二
• • 思路
  • 代碼

二叉樹的最近公共祖先

題目

點(diǎn)擊跳轉(zhuǎn)：LeetCode

思路一

思路

從題目中的描述可以發(fā)現(xiàn)如下規(guī)律

• 如果結(jié)點(diǎn)p和結(jié)點(diǎn)q在分別在root結(jié)點(diǎn)的左右子樹，那么root結(jié)點(diǎn)便是p和q的最近公共祖先
• 如果結(jié)點(diǎn)p和結(jié)點(diǎn)q都在root結(jié)點(diǎn)的左子樹，那么就要到左子樹中尋找；相反就要去右子樹中尋找
• 某次尋找時(shí)如果出現(xiàn)了root==q或root==p的情況，例如示例中的結(jié)點(diǎn)5和結(jié)點(diǎn)4，那么此時(shí)root結(jié)點(diǎn)就是最近高公共祖先

代碼

class Solution { public:bool Find(TreeNode* root,TreeNode* target)//找尋某個(gè)結(jié)點(diǎn)是否存在{if(root==nullptr)return false;if(root==target)return true;return Find(root->left,target) || Find(root->right,target);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr)return nullptr;if(root==p || root==q)//上圖中結(jié)點(diǎn)5和結(jié)點(diǎn)4的情況return root;//定義4個(gè)布爾類型，用于判斷p在root左面還是右面，q在root的左面還是右面bool pInleft,pInright,qInleft,qInright;pInleft=Find(root->left,p);pInright=!pInleft;qInleft=Find(root->left,q);qInright=!qInleft;if((pInleft && qInright) || (pInright && qInleft))//如果p和q分別在root的左（右）和右（左），那么root就是最近公共祖先{return root;}else if(pInleft && qInleft)//如果p和q在root的左面，那么就遞歸到左子樹尋找{return lowestCommonAncestor(root->left,p,q);}else//如果p和q在root的右面，那么就遞歸到右子樹尋找return lowestCommonAncestor(root->right,p,q);} };

思路二

思路

可以使用兩個(gè)棧pPath和qPath，分別保存結(jié)點(diǎn)p和結(jié)點(diǎn)q的所有祖先，然后這道題實(shí)際就轉(zhuǎn)化為了鏈表相交的那道題，當(dāng)pPath.size()==qPaht.size()時(shí)，棧頂就是最近公共祖先

代碼

class Solution { public:bool Find(TreeNode* root,TreeNode* x,stack<TreeNode*>& path){if(root==nullptr)return false;path.push(root);//如果root不等于nullptr，那么先入棧if(root==x)//如果恰好root就是要找的結(jié)點(diǎn)，那么直接返回return true;if(Find(root->left,x,path))//如果root不是要找的結(jié)點(diǎn)，那么x結(jié)點(diǎn)可能存在于root的左子樹或右子樹中，所以遞歸return true;if(Find(root->right,x,path))return true;path.pop();//如果運(yùn)行到這里還沒有找到，說明root不可能是x的一個(gè)祖先return false;//所以返回false}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath;//結(jié)點(diǎn)p的所有祖先存放在這個(gè)棧里面stack<TreeNode*> qPath;//結(jié)點(diǎn)q的所有祖先存放在這個(gè)棧里面Find(root,p,pPath);Find(root,q,qPath);//不知道哪個(gè)棧長，反正讓它們相等即可while(pPath.size() > qPath.size())pPath.pop();while(qPath.size() > pPath.size())qPath.pop();while(pPath.top()!=qPath.top())//當(dāng)棧頂元素相等時(shí)，此時(shí)保存的就是最近公共祖先{pPath.pop();qPath.pop();}return pPath.top();} };

總結(jié)

以上是生活随笔為你收集整理的二叉树经典题之二叉树最近公共祖先（LeetCode）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。