文章目錄
- 最近公共祖先定義
- 查找最近公共祖先
- 三叉鍊
- 二叉搜尋樹
- 普通二叉樹
最近公共祖先定義
查找最近公共祖先
三叉鍊
代碼如下：
//三叉鍊
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* curp = p, *curq = q; //用于周遊p、q結點的祖先結點
int lenp = 0, lenq = 0; //分别記錄p、q結點各自的祖先結點個數
//統計p結點的祖先結點個數
while (curp != root)
{
lenp++;
curp = curp->parent;
}
//統計q結點的祖先結點個數
while (curq != root)
{
lenq++;
curq = curq->parent;
}
//longpath和shortpath分别标記祖先路徑較長和較短的結點
TreeNode* longpath = p, *shortpath = q;
if (lenp < lenq)
{
longpath = q;
shortpath = p;
}
//p、q結點祖先結點個數的內插補點
int count = abs(lenp - lenq);
//先讓longpath往上走count個結點
while (count--)
{
longpath = longpath->parent;
}
//再讓longpath和shortpath同時往上走，此時第一個相同的結點便是最近公共祖先結點
while (longpath != shortpath)
{
longpath = longpath->parent;
shortpath = shortpath->parent;
}
return longpath; //傳回最近公共祖先結點
}
}; 二叉搜尋樹
代碼如下：
//搜尋二叉樹
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 (p->val == root->val || q->val == root->val) //p、q結點中某一個結點的值等于根結點的值，則根結點就是這兩個結點的最近公共祖先
return root;
if (p->val < root->val&&q->val < root->val) //p、q結點的值都小于根結點的值，說明這兩個結點的最近公共祖先在該樹的左子樹當中
return lowestCommonAncestor(root->left, p, q);
else if (p->val > root->val&&q->val > root->val) //p、q結點的值都大于根結點的值，說明這兩個結點的最近公共祖先在該樹的右子樹當中
return lowestCommonAncestor(root->right, p, q);
else //p、q結點的值一個比根小一個比根大，說明根就是這兩個結點的最近公共祖先
return root;
}
}; 普通二叉樹
代碼如下：
//普通二叉樹
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool Find(TreeNode* root, TreeNode* x)
{
if (root == nullptr) //空樹，查找失敗
return false;
if (root == x) //查找成功
return true;
return Find(root->left, x) || Find(root->right, x); //在左子樹找到了或是右子樹找到了，都說明該結點在該樹當中
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p == root || q == root) //p、q結點中某一個結點為根結點，則根結點就是這兩個結點的最近公共祖先
return root;
//判斷p、q結點是否在左右子樹
bool IspInLeft, IspInRight, IsqInLeft, IsqInRight;
IspInLeft = Find(root->left, p);
IspInRight = !IspInLeft;
IsqInLeft = Find(root->left, q);
IsqInRight = !IsqInLeft;
if (IspInLeft&&IsqInLeft) //p、q結點都在左子樹，說明這兩個結點的最近公共祖先也在左子樹當中
return lowestCommonAncestor(root->left, p, q);
else if (IspInRight&&IsqInRight) //p、q結點都在右子樹，說明這兩個結點的最近公共祖先也在右子樹當中
return lowestCommonAncestor(root->right, p, q);
else //p、q結點一個在左子樹一個在右子樹，說明根就是這兩個結點的最近公共祖先
return root;
}
}; 看着似乎不太好了解，來看看下面的動圖示範：
//普通二叉樹
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
if (root == nullptr)
return false;
path.push(root); //該結點可能是路徑當中的結點，先入棧
if (root == x) //該結點是最終結點，查找結束
return true;
if (FindPath(root->left, x, path)) //在該結點的左子樹找到了最終結點，查找結束
return true;
if (FindPath(root->right, x, path)) //在該結點的右子樹找到了最終結點，查找結束
return true;
path.pop(); //在該結點的左右子樹均沒有找到最終結點，該結點不可能是路徑當中的結點，該結點出棧
return false; //在該結點處查找失敗
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath, qPath;
FindPath(root, p, pPath); //将從根到p結點的路徑存放到pPath當中
FindPath(root, q, qPath); //将從根到q結點的路徑存放到qPath當中
//longpath和shortpath分别标記長路徑和短路徑
stack<TreeNode*>* longPath = &pPath, *shortPath = &qPath;
if (pPath.size() < qPath.size())
{
longPath = &qPath;
shortPath = &pPath;
}
//讓longPath先彈出內插補點個資料
int count = longPath->size() - shortPath->size();
while (count--)
{
longPath->pop();
}
//longPath和shortPath一起彈資料，直到兩個棧頂的結點相同
while (longPath->top() != shortPath->top())
{
longPath->pop();
shortPath->pop();
}
return longPath->top(); //傳回這個相同的結點，即最近公共祖先
}
};