漫画讲解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语言 公共祖先内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-11-22

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

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

深入二叉树两个结点的最低共同父结点的详解

题目:二叉树的结点定义如下: 复制代码 代码如下: struct TreeNode   {              int m_nvalue;             TreeNode* m_pLeft;             TreeNode* m_pRight;}; 输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点.分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题.这个问题至少有两个变种.第一变种是二叉树是一种特殊的二叉树:查找二叉树.也就是树是排序过的,位于左子

C语言数据结构二叉树简单应用

 C语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

C++基于递归和非递归算法求二叉树镜像的方法

本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

Java编程求二叉树的镜像两种方法介绍

给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

Java语言描述二叉树的深度和宽度

解释: 二叉树的深度:从根结点到叶结点依次经过的结点(含根.叶结点)形成树的一条路径,最长路径的长度为树的深度. 二叉树的宽度:二叉树的每一层中都有一定数量的节点,节点数最多的那一层的节点数叫做二叉树的宽度. 思路:递归实现. 1.每个节点都可以看作根节点 2.根节点(任意一个节点)的深度等于它的左子树或右子树深度最大值+1 3.从根结点开始遍历,若遍历到叶子节点,深度为0 //二叉树的深度 public static int Depth(node root){ if(root == null)

java编程求二叉树最大路径问题代码分析

题目: Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. 节点可能为负数,寻找一条最路径使得所经过节点和最大.路径可以开始和结束于任何节点但是不能走回头路. 这道题虽然

C语言判定一棵二叉树是否为二叉搜索树的方法分析

本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n

C语言实现带头结点的链表的创建、查找、插入、删除操作

本文实例讲述了C语言实现带头结点的链表的创建.查找.插入.删除操作.是数据结构中链表部分的基础操作.分享给大家供大家参考.具体方法如下: #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next;// 这个地方注意结构体变量的定义规则 } Node, *PNode; Node* createLinklist(int length) { int i = 0; PNo

C语言实现二叉树遍历的迭代算法

本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le