- 浏览: 21248 次
- 性别:
- 来自: 南京
最新评论
二叉树中的最近公共祖先问题
- 博客分类:
- 算法
题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。
view sourceprint?1 class Node
2 {
3 Node * left;
4 Node * right;
5 Node * parent;
6 };
7 /*查找p,q的最近公共祖先并将其返回。*/
8 Node * NearestCommonAncestor(Node * p,Node * q);
算法思想:这道题的关键在于每个节点中包含指向父节点的指针,这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent,然后将q的所有父节点依次和p->parent作比较,如果发现两个节点相等,则该节点就是最近公共祖先,直接将其返回。如果没找到相等节点,则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。
程序代码:
view sourceprint?01 Node * NearestCommonAncestor(Node * root,Node * p,Node * q)
02 {
03 Node * temp;
04 while(p!=NULL)
05 {
06 p=p->parent;
07 temp=q;
08 while(temp!=NULL)
09 {
10 if(p==temp->parent)
11 return p;
12 temp=temp->parent;
13 }
14 }
15 }
题目:将一个单链表逆转——原来的头指针变为尾指针,原来的尾指针变为头指针。
算法思想:从链表的头结点开始依次逆转,最终将整个链表逆转。
程序代码:
view sourceprint?01 /*节点的类定义*/
02 class Node
03 {
04 Node * next;
05 };
06
07 /*链表的类定义*/
08 class List
09 {
10 Node * head;
11 };
12
13 /*逆转函数——将一个单链表逆转*/
14 void ReverseList(List & list)
15 {
16 Node * pre=NULL;
17 Node * cur=list.head;
18 Node * back=cur->next;
19
20 while(back!=NULL)
21 {
22 cur->next=pre;
23 pre=cur;
24 cur=back;
25 back=cur->next;
26 }
27
28 }
知识拓展:对于第二个二叉树的问题,如果节点中不包含指向父节点的指针应该怎么计算?
算法思想:如果一个节点的左子树包含p,q中的一个节点,右子树包含另一个,则这个节点就是p,q的最近公共祖先。
程序代码:
view sourceprint?01 /*查找a,b的最近公共祖先,root为根节点,out为最近公共祖先的指针地址*/
02 int FindNCA(Node* root, Node* a, Node* b, Node** out)
03 {
04 if( root == null )
05 {
06 return 0;
07 }
08
09 if( root == a || root == b )
10 {
11 return 1;
12 }
13
14 int iLeft = FindNCA(root->left, a, b, out);
15 if( iLeft == 2 )
16 {
17 return 2;
18 }
19
20 int iRight = FindNCA(root->right, a, b, out);
21 if( iRight == 2 )
22 {
23 return 2;
24 }
25
26 if( iLeft + iRight == 2 )
27 {
28 *out == root;
29 }
30 return iLeft + iRight;
31 }
32
33 void main()
34 {
35 Node* root = ...;
36 Node* a = ...;
37 Node* b = ...;
38 Node* out = null;
39 int i = FindNCA(root, a, b, &out);
40 if( i == 2 )
41 {
42 printf("Result pointer is %p", out);
43 }
44 else
45 {
46 printf("Not find pointer");
47 }
48 }
view sourceprint?1 class Node
2 {
3 Node * left;
4 Node * right;
5 Node * parent;
6 };
7 /*查找p,q的最近公共祖先并将其返回。*/
8 Node * NearestCommonAncestor(Node * p,Node * q);
算法思想:这道题的关键在于每个节点中包含指向父节点的指针,这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent,然后将q的所有父节点依次和p->parent作比较,如果发现两个节点相等,则该节点就是最近公共祖先,直接将其返回。如果没找到相等节点,则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。
程序代码:
view sourceprint?01 Node * NearestCommonAncestor(Node * root,Node * p,Node * q)
02 {
03 Node * temp;
04 while(p!=NULL)
05 {
06 p=p->parent;
07 temp=q;
08 while(temp!=NULL)
09 {
10 if(p==temp->parent)
11 return p;
12 temp=temp->parent;
13 }
14 }
15 }
题目:将一个单链表逆转——原来的头指针变为尾指针,原来的尾指针变为头指针。
算法思想:从链表的头结点开始依次逆转,最终将整个链表逆转。
程序代码:
view sourceprint?01 /*节点的类定义*/
02 class Node
03 {
04 Node * next;
05 };
06
07 /*链表的类定义*/
08 class List
09 {
10 Node * head;
11 };
12
13 /*逆转函数——将一个单链表逆转*/
14 void ReverseList(List & list)
15 {
16 Node * pre=NULL;
17 Node * cur=list.head;
18 Node * back=cur->next;
19
20 while(back!=NULL)
21 {
22 cur->next=pre;
23 pre=cur;
24 cur=back;
25 back=cur->next;
26 }
27
28 }
知识拓展:对于第二个二叉树的问题,如果节点中不包含指向父节点的指针应该怎么计算?
算法思想:如果一个节点的左子树包含p,q中的一个节点,右子树包含另一个,则这个节点就是p,q的最近公共祖先。
程序代码:
view sourceprint?01 /*查找a,b的最近公共祖先,root为根节点,out为最近公共祖先的指针地址*/
02 int FindNCA(Node* root, Node* a, Node* b, Node** out)
03 {
04 if( root == null )
05 {
06 return 0;
07 }
08
09 if( root == a || root == b )
10 {
11 return 1;
12 }
13
14 int iLeft = FindNCA(root->left, a, b, out);
15 if( iLeft == 2 )
16 {
17 return 2;
18 }
19
20 int iRight = FindNCA(root->right, a, b, out);
21 if( iRight == 2 )
22 {
23 return 2;
24 }
25
26 if( iLeft + iRight == 2 )
27 {
28 *out == root;
29 }
30 return iLeft + iRight;
31 }
32
33 void main()
34 {
35 Node* root = ...;
36 Node* a = ...;
37 Node* b = ...;
38 Node* out = null;
39 int i = FindNCA(root, a, b, &out);
40 if( i == 2 )
41 {
42 printf("Result pointer is %p", out);
43 }
44 else
45 {
46 printf("Not find pointer");
47 }
48 }
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 662最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1058在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 891排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1338求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 721题目:在节假日的时候 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 574给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 939在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 755最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
Java语言,通过栈的方法建立二叉树,递归求最近共同祖先结点
本程序为VS2010编写,其中包含两种方法实现此题目。
设计一个算法,对于给定的树中2 结点返回它们的最近公共祖先。 对于给定的树,和树中结点对,编程计算结点对的最近公共祖先。
C语言所写源代码有注释,哈工大数据结构实验课自己所作,仅供参考
剑指 Offer 68 - II. 二叉树的最近公共祖先原题链接:剑指 Offer 68 - II. 二叉树的最近公共祖先代码public TreeNode l
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
1、 如果结点 p、q 都存在且为左右结点,那么根结点 root 就是最近公共祖先 2、 如果结点 p、q 都存在且都为左结点,那么在根结点 root 的左子树
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)” 例如,给定如下二叉树: root = [3...
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节
在利用栈建立一个二叉树的基础上,我们可以通过递归来实现二叉树中两个结点的最近公共祖先结点。递归是一种非常强大的算法技巧,它可以通过反复调用自身来解决问题。在这个特定的问题中,我们可以利用递归来查找两个...
主要介绍了使用C语言求二叉树结点的最低公共祖先的方法,文中还给出了ACM的练习题目,需要的朋友可以参考下
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 ...6. 所需的素质:扎实的基础知识、能写高质量的代码、分析问题是思路清晰、能优化时间和空间效率、学习沟通能力
3.6 Git 原理之二叉树最近公共祖先本文对应的力扣题目:236.二叉树的最近公共祖先// 情况 1// 情况 2// 情况 3return left ==
剩下即为从起点和终点的最近公共祖先出发,到起点和终点的路径我们要找的最短路径即为:起点 => 起点和终点的最近公共祖先 => 终点。答案为:起点 => 公共祖先
难度:简单 一、题目描述: 二、解题分析: # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: ...
数据结构用C语言描述,第六章树和二叉树课后练习题,求最近的公共祖先,源代码答案。
在利用栈建立一个二叉树的基础上,我们可以通过递归来实现二叉树中两个结点的最近公共祖先结点。递归是一种非常强大的算法技巧,它可以通过反复调用自身来解决问题。在这个特定的问题中,我们可以利用递归来查找两个...