漫画讲解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; //返回最近公共祖先结点
	}
};

二叉搜索树

代码如下:

//搜索二叉树
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(); //返回这个相同的结点,即最近公共祖先
	}
};

到此这篇关于漫画讲解C语言中最近公共祖先的三种类型的文章就介绍到这了,更多相关C语言 公共祖先内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 使用C语言求二叉树结点的最低公共祖先的方法

    算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

  • 漫画讲解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* ro

  • C/C++程序开发中实现信息隐藏的三种类型

    无论是模块化设计,还是面向对象设计,还是分层设计,实现子系统内部信息的对外隐藏都是最关键的内在要求.以本人浅显的经验,把信息隐藏按照程度的不同分成(1)不可见不可用(2)可见不可用(3)可见可用. 1 不可见不可用 就是说模块内部的变量.结构体.类定义对外部而已完全隐藏,外部对此一无所知.常用的实现方法就是利用不透明指针,请参见我的博文C语言开发函数库时利用不透明指针对外隐藏结构体细节. 这种方法同样适用于C++语言,一种可能的实现方式为面向接口编程. 头文件 IMyClass.h class

  • 通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

    详解二叉树的三种非递归遍历方式(附C.java源码) 前言 二叉树的递归遍历方式很简单,三种递归遍历方式的区别,只是printf放的位置不一样而已,这里就不多讲了.把前序遍历代码贴在这里: //结点 struct Node { int val; struct Node* left, * right; }; //前序遍历 void pre(Node* root) { if (root == null) return; printf("%d ",root->val); pre(roo

  • C语言中对数组赋值的三种形式

    前言 C 语言支持数组数据结构,它可以存储一个固定大小的相同类型元素的顺序集合.数组是用来存储一系列数据,但它往往被认为是一系列相同类型的变量. 在C语言中,对数组进行赋值的三种形式 方法如下: 1.通过循环的形式     即:数组名[下标]      对数组的元素进行依次赋值 #include <stdio.h> int main() { int i; int a[10] = {0}; for(i=0;i<10;i++) { scanf("%d",&a[i]

  • 深入讲解Go语言中函数new与make的使用和区别

    前言 本文主要给大家介绍了Go语言中函数new与make的使用和区别,关于Go语言中new和make是内建的两个函数,主要用来创建分配类型内存.在我们定义生成变量的时候,可能会觉得有点迷惑,其实他们的规则很简单,下面我们就通过一些示例说明他们的区别和使用,话不多说了,来一起看看详细的介绍吧. 变量的声明 var i int var s string 变量的声明我们可以通过var关键字,然后就可以在程序中使用.当我们不指定变量的默认值时,这些变量的默认值是他们的零值,比如int类型的零值是0,st

  • Go语言中的方法、接口和嵌入类型详解

    概述 在 Go 语言中,如果一个结构体和一个嵌入字段同时实现了相同的接口会发生什么呢?我们猜一下,可能有两个问题: 1.编译器会因为我们同时有两个接口实现而报错吗? 2.如果编译器接受这样的定义,那么当接口调用时编译器要怎么确定该使用哪个实现? 在写了一些测试代码并认真深入的读了一下标准之后,我发现了一些有意思的东西,而且觉得很有必要分享出来,那么让我们先从 Go 语言中的方法开始说起. 方法 Go 语言中同时有函数和方法.一个方法就是一个包含了接受者的函数,接受者可以是命名类型或者结构体类型的

  • Java中获取键盘输入值的三种方法介绍

    程序开发过程中,需要从键盘获取输入值是常有的事,但Java它偏偏就没有像c语言给我们提供的scanf(),C++给我们提供的cin()获取键盘输入值的现成函数!Java没有提供这样的函数也不代表遇到这种情况我们就束手无策,请你看以下三种解决方法吧: 以下将列出几种方法: 方法一:从控制台接收一个字符,然后将其打印出来 public static void main(String [] args) throws IOException{ System.out.print("Enter a char

  • Go语言net包RPC远程调用三种方式http与json-rpc及tcp

    目录 一.服务端 二.http客户端 三.TCP客户端 四.json客户端 五.运行结果 rpc有多种调用方式,http.json-rpc.tcp 一.服务端 在代码中,启动了三个服务 package main import ( "log" "net" "net/http" "net/rpc" "net/rpc/jsonrpc" "sync" ) //go对RPC的支持,支持三个级别:T

  • C语言实现求最大公约数的三种方法

    目录 题目描述 问题分析 代码实现 方法一:穷举法 方法二:辗转相除法 方法三:更相减损法 题目描述 求任意两个正整数的最大公约数 问题分析 最大公因数,也称最大公约数.最大公因子,指两个或多个整数共有约数中最大的一个.a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号.求最大公约数有多种方法,常见的有质因数分解法.短除法.辗转相除法.更相减损法.与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]. --百度

  • C语言结构体数组常用的三种赋值方法(包含字符串)

    目录 一.按照成员变量进行赋值(麻烦,好理解,字符串赋值需要strcpy) 二.对数组整体进行赋值.(一次性需要把所有的都添加进去,不需要strcpy) (1) 在声明数组的时候,进行赋值 (2)对有规律的数据赋值,比如学生结构体的学号是有规律的. 三.使用输入进行赋值 总结 一.按照成员变量进行赋值(麻烦,好理解,字符串赋值需要strcpy) 这里使用了一个Init函数,为了在进一步说明传参的使用.实际上赋值按照需要放在主函数就行. (使用strcpy函数需要添加头文件string.h) #i

随机推荐