这篇文章主要总结了使用C语言查找最近公共祖先的三种方法类型,用漫画的方式讲解原理定义,看上去更生动形象,帮助你更好的理解透彻,快来跟着本文往下看吧


最近公共祖先定义


查找最近公共祖先





三叉链




代码如下:
//三叉链
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; //返回最近公共祖先结点
}
};

发表评论