給定一個二叉樹, 找到該樹中兩個指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點(diǎn) p、q，最近公共祖先表示為一個結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點(diǎn)也可以是它自己的祖先）。”

例如，給定如下二叉樹:??root =?[3,5,1,6,2,0,8,null,null,7,4]

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3。
示例?2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。

說明:

所有節(jié)點(diǎn)的值都是唯一的。
p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹中。

?方法1：第一遍只能想到這個笨辦法了，按行遍歷，把包含兩個節(jié)點(diǎn)的節(jié)點(diǎn)保存下來，取最后一個公共節(jié)點(diǎn)。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:queue<TreeNode*> commonNodes;TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*> nodes;if(root==NULL)return NULL;nodes.push(root);while(!nodes.empty()){TreeNode* front = nodes.front();nodes.pop();if(isexist_p(front,p)&&isexist_q(front,q))commonNodes.push(front);if(front->left) nodes.push(front->left);if(front->right) nodes.push(front->right);}return commonNodes.back();}bool isexist_p(TreeNode* root, TreeNode* p){if(root==p){return true;}if(root==NULL){return false;}return isexist_p(root->right,p) || isexist_p(root->left,p);}bool isexist_q(TreeNode* root, TreeNode* q){if(root==q){return true;}if(root==NULL){return false;}return isexist_q(root->right,q) || isexist_q(root->left,q);} };

解法二：

做了一些二叉樹的題，發(fā)現(xiàn)二叉樹的查找問題一般都是從左右子樹遞歸去解決，也往往都能得到答案，因此，這道題可以考慮是否能從左右子樹進(jìn)行遞歸去解決呢？
首先，要想通過遞歸來實(shí)現(xiàn)，就需要先確定臨界條件，那么臨界條件是什么呢？換句話說，臨界條件就是遞歸中能夠直接返回的特殊情況，第一點(diǎn)則是最常見的“判空”，判斷根結(jié)點(diǎn)是否是空節(jié)點(diǎn)，如果是，那么肯定就可以馬上返回了，這是一個臨界條件；再來考慮題意，在以root為根結(jié)點(diǎn)的樹中找到p結(jié)點(diǎn)和q結(jié)點(diǎn)的最近公共祖先，那么特殊情況是什么呢？很顯然，特殊情況就是根結(jié)點(diǎn)就等于q結(jié)點(diǎn)或p結(jié)點(diǎn)的情況，想一下，如果根結(jié)點(diǎn)為二者之一，那么根結(jié)點(diǎn)就必定是最近公共祖先了，這時直接返回root即可。由此看來，這道題就一共有三種特殊情況，root == q 、root == p和root==null，這三種情況均直接返回root即可。
根據(jù)臨界條件，實(shí)際上可以發(fā)現(xiàn)這道題已經(jīng)被簡化為查找以root為根結(jié)點(diǎn)的樹上是否有p結(jié)點(diǎn)或者q結(jié)點(diǎn)，如果有就返回p結(jié)點(diǎn)或q結(jié)點(diǎn)，否則返回null。
這樣一來其實(shí)就很簡單了，從左右子樹分別進(jìn)行遞歸，即查找左右子樹上是否有p結(jié)點(diǎn)或者q結(jié)點(diǎn)，就一共有4種情況：
第一種情況：左子樹和右子樹均找沒有p結(jié)點(diǎn)或者q結(jié)點(diǎn)；（這里特別需要注意，雖然題目上說了p結(jié)點(diǎn)和q結(jié)點(diǎn)必定都存在，但是遞歸的時候必須把所有情況都考慮進(jìn)去，因?yàn)轭}目給的條件是針對于整棵樹，而遞歸會到局部，不一定都滿足整體條件）
第二種情況：左子樹上能找到，但是右子樹上找不到，此時就應(yīng)當(dāng)直接返回左子樹的查找結(jié)果；
第三種情況：右子樹上能找到，但是左子樹上找不到，此時就應(yīng)當(dāng)直接返回右子樹的查找結(jié)果；
第四種情況：左右子樹上均能找到，說明此時的p結(jié)點(diǎn)和q結(jié)點(diǎn)分居root結(jié)點(diǎn)兩側(cè)，此時就應(yīng)當(dāng)直接返回root結(jié)點(diǎn)了。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root==p||root==q)return root;if (root==NULL)return NULL;TreeNode* lNode=lowestCommonAncestor(root->left,p,q);TreeNode* rNode=lowestCommonAncestor(root->right,p,q);if(lNode!=NULL&&rNode!=NULL)return root;else if(lNode==NULL)//兩個都在右子樹return rNode;else//兩個都在左子樹里面return lNode;return NULL;} };

?

總結(jié)

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

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