目錄
題目：
示例：
分析：
代碼：
題目：
示例：
分析：
?給我們一棵二叉樹，然后給我們pq兩個節(jié)點，讓我們找出二叉樹中它們倆的最近的公共祖先。
那么什么樣的節(jié)點是它們倆的最近的公共祖先呢，是有兩種情況，第一種情況的pq兩個節(jié)點都在同一條路徑上，像下圖這樣：
?那這時pq的最近公共祖先就是pq之中更靠進上層的那個節(jié)點，也就是pq之中有個節(jié)點是自己的祖先節(jié)點。
另一種情況就是，他們分布在它們公共祖先的左右兩側，也就是pq里其中一個在最近公共祖先的左子樹上，另一個在最近公共祖先的右子樹上，像下圖這樣：
?因為pq已經各自分布在這個節(jié)點的左右兩側了，如果這個節(jié)點再往下走，不管是走哪個方向，都不可能再同時是它們兩個節(jié)點的公共祖先了。
所以我們在遞歸遍歷二叉樹的時候，一旦發(fā)現(xiàn)了pq分布在某個節(jié)點的左右兩側，或是直接遍歷到了pq節(jié)點，那就將當前節(jié)點返回出去即可。
我們做常規(guī)的遍歷二叉樹，并且再遍歷里頭再套一層遞歸遍歷分別去當前節(jié)點的左子樹和右子樹尋找是否有pq節(jié)點。
在遞歸遍歷之前先檢測當前節(jié)點是否是pq之一，是的話直接返回當前節(jié)點。
如果pq分別分布在當前節(jié)點的左右子樹，那么也直接返回當前節(jié)點。
最后一種情況就是，pq分布在當前節(jié)點的同一側。
?
文章來源：http://www.zghlxwxcb.cn/news/detail-677237.html
這時候雖然當前節(jié)點也還是兩個節(jié)點的公共祖先，但并不是最近的公共祖先，并且因為pq都在當前節(jié)點的某棵子樹上（左子樹或是右子樹），那么它們的最近公共祖先必然是在當前節(jié)點的子樹，所以在我們需要將當前節(jié)點向那棵子樹上轉移，直到出現(xiàn)上面第一第二種情況。
文章來源地址http://www.zghlxwxcb.cn/news/detail-677237.html
代碼：
class Solution {
public:
bool find(TreeNode* root,TreeNode*p,TreeNode* q){ //尋找是否有pq
if(root==nullptr) return false;
if(root==p || root==q) return true;
return find(root->left,p,q)||find(root->right,p,q);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==p||root==q) return root;
TreeNode* res=root;
bool l=find(root->left,p,q);bool r=find(root->right,p,q);
while(l||r){
//如果自己本身就是其中一個節(jié)點,那么直接返回即可
if(res==p||res==q) return res;
if(l&&!r){ //如果pq全部集中在左子樹,就往左子樹移動
res=res->left;
}else if(r&&!l){ //如果pq全部集中在右子樹,就往右子樹移動
res=res->right;
}else{ //如果是左右各占一個,那么返回該節(jié)點
return res;
}
//尋找pq的分布情況
l=find(res->left,p,q);
r=find(res->right,p,q);
}
return root;
}
};到了這里，關于【LeetCode75】第三十八題 二叉樹的最近公共祖先的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
