求树中两个结点的最近公共祖先

剑指offer上的最后一题了,一个递归函数调了一下午,才得到正确的结果。

题目描述:

给定一棵树,同时给出树中的两个结点,求它们的最低公共祖先。

输入:

输入可能包含多个测试样例。

对于每个测试案例,输入的第一行为一个数n(0<n<1000),代表测试样例的个数。

其中每个测试样例包括两行,第一行为一个二叉树的先序遍历序列,其中左右子树若为空则用0代替,其中二叉树的结点个数node_num<10000。

第二行为树中的两个结点的值m1与m2(0<m1,m2<10000)。

输出:

对应每个测试案例,

输出给定的树中两个结点的最低公共祖先结点的值,若两个给定结点无最低公共祖先,则输出“My God”。

样例输入:

2

1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0

6 8

1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0

6 12

样例输出:

2

My God

这类的题目,方法蛮多的,思路也不难理解,基本都是各种遍历的变种,主要是写代码,尤其基于递归的代码。

首先如果是二叉排序树自然不用说了,判断的一句就是该节点的值是否位于输入的这两个节点之间,可以用前序遍历来做。

如果是普通的树或者二叉树,解题思路是一样的,可以考虑前序遍历,得到两个路径,用链表或数组保存起来,然后找出两条路径的最后一个公共节点即可。也可以后序遍历的方式,遍历到输入的节点时,将该节点及其后面遍历到的节点都保存到一个链表或数组中,然后找出两条路径的第一个公共机节点即可。

下面采用的是前序遍历,并用数组保存路径的代码。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>  

typedef struct BTNode
{
    struct BTNode *lchild;
    struct BTNode *rchild;
    int data;
}BTNode,*BTree;  

/*
前序遍历找出根节点到数据域为val的节点路径,保存在path数组中,
返回栏目页:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
这里index是保存到path数组中的元素的下标,*len用来保存路径长度,
如果能找到val,则返回ture,找不到则返回false
*/
bool GetPreTraversePath(BTree pTree,int val,int *path,int index,int *len)
{
    if(pTree == NULL)
    {
        *len = 0;
        return false;
    }  

    path[index] = pTree->data;
    if(pTree->data == val)
    {
        *len = index+1;
        return true;
    }
    else
    {
        bool can;
        can = GetPreTraversePath(pTree->lchild,val,path,index+1,len);
        if(!can)
            can = GetPreTraversePath(pTree->rchild,val,path,index+1,len);
        return can;
    }
}  

/*
获取两个路径的最后一个公共节点,
由于对树的先序遍历的结果中,前面一定有些节点相同,因此一定能找到最后一个相同节点
*/
int GetFirstCommonNode(int *path1,int len1,int *path2,int len2)
{
    int shortLen = len1<len2 ? len1:len2;
    int i;
    for(i=0;i<shortLen;i++)
    {
        if(path1[i] != path2[i])
            break;
    }
    return path1[i-1];
}  

/*
根据先序遍历序列创建二叉树,由于可能改变根节点的指向,因此传入BTNode的二级指针
*/
void CreateBTree(BTree *pRoot)
{
    int data;
    scanf("%d",&data);
    if(data == 0)
        *pRoot = NULL;
    else
    {
        *pRoot = (BTree)malloc(sizeof(BTNode));
        if(*pRoot == NULL)
            exit(EXIT_FAILURE);
        (*pRoot)->data = data;
        (*pRoot)->lchild = NULL;
        (*pRoot)->rchild = NULL;
        CreateBTree(&((*pRoot)->lchild));
        CreateBTree(&((*pRoot)->rchild));
    }
}  

/*
销毁二叉树
*/
void DestroyBTree(BTree pRoot)
{
    if(pRoot != NULL)
    {
        if(pRoot->lchild != NULL)
            DestroyBTree(pRoot->lchild);
        if(pRoot->rchild != NULL)
            DestroyBTree(pRoot->rchild);
        free(pRoot);
        pRoot = NULL;
    }
}  

int main()
{
    int path1[10000];
    int path2[10000];  

    int n;
    while(scanf("%d",&n) != EOF)
    {
        int i;
        for(i=0;i<n;i++)
        {
            BTree pRoot = NULL;
            CreateBTree(&pRoot);  

            int val1,val2;
            scanf("%d %d",&val1,&val2);  

            int len1,len2;
            bool can1 = GetPreTraversePath(pRoot,val1,path1,0,&len1);
            bool can2 = GetPreTraversePath(pRoot,val2,path2,0,&len2);  

            if(can1 && can2)
                printf("%d\n",GetFirstCommonNode(path1,len1,path2,len2));
            else
                printf("My God\n");  

            DestroyBTree(pRoot);
        }
    }
    return 0;
}

/**************************************************************

Problem: 1509

User: mmc_maodun

Language: C

Result: Accepted

Time:130 ms

Memory:920 kb

****************************************************************/

PS:寻找路径的递归代码调了一个下午,总算搞定了,每次碰到关于树的问题,一般都是三种遍历方式的变种来实现,自然想到递推,有些写着很容易,有些写着总很纠结,尤其要返回bool变量的时候,还是太菜,回头要抽个时间把二叉树的递归实现的一些题目好好总结下。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索递归
, int
, null
, 结点
输入
最近公共祖先、最近公共祖先 倍增、二叉树最近公共祖先、lca最近公共祖先、最近公共祖先 tarjan,以便于您获取更多的相关知识。

时间: 2024-09-12 07:43:17

求树中两个结点的最近公共祖先的相关文章

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

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

[算法系列之三十一]最近公共祖先(LCA)

[简介] 对于有根树T的两个结点u.v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u.v的祖先且x的深度尽可能大. 另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点. 例如,对于下面的树,结点4和结点6的最近公共祖先LCA(T,4,6)为结点2. 求树中两个结点的最低公共祖先是面试中经常出现的一个问题.一般的做法,可能是针对是否为二叉查找树分情况讨论. LCA问题的扩展主要在于结点是否只包含父结点指针,对于同一棵树是否进行多次LCA查询

【14】最近公共祖先问题

题目:给定一颗二叉树的两个结点,求这两个结点的最近公共祖先结点 分析:1. 假如二叉树是二叉排序树                根据二叉排序树的性质,左子树结点的值小于根结点,根结点的值小于右子树结点的值                那么每次只要判断,给定的两个结点的值和左右结点的值比较即可                如果两个值都小于根结点的值,则递归到左子树                如果两个值都大于根结点的值,则递归到右子树                否则根结点即为最近公共祖

java实现求两个字符串最长公共子串的方法_java

本文实例讲述了java实现求两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: 这个是华为OJ上的一道题目.首先,如果我们用java写代码,华为OJ有以下三条规则需遵守,否则编译无法通过或者用例无法通过,规则如下: (1)一定不可以有包名: (2)主类名只能为Main: (3)不可以输出与结果无关的信息. 好了,按照以上规则,我们写出来的代码如下(此代码不是最优的,只是用来记录华为OJ上java代码的书写规则): import java.util.Scanner; public cl

语言-试编写算法,求二叉树T中结点a和b的最近共同祖先。

问题描述 试编写算法,求二叉树T中结点a和b的最近共同祖先. 试编写算法,求二叉树T中结点a和b的最近共同祖先.二叉链表类型定义:typedef struct BiTNode { TElemType data; struct BiTNode lchild*rchild;} BiTNode *BiTree;可用栈类型Stack的相关定义:typedef struct { BiTNode *ptr; // 二叉树结点的指针类型 int tag; // 0..1} SElemType; // 栈的元素

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

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

c语言-求教编写一个函数求出两个字符串包含的相同的单词

问题描述 求教编写一个函数求出两个字符串包含的相同的单词 编写一个函数,函数首部为void maxword(char *s,char *t),求出两个字符串包含的相同单词(同一字母的大小写视为不同的字符).规定单词全部由英文字母构成,单词直接由一个或多个空格分隔.其中主函数如下: #include Void main() { Char s[]="This is C programming text"; Char t[]="This is a text for C progra

求任意两个节点之间有几条通路

问题描述 求任意两个节点之间有几条通路 输入一些二元组,二元组代表两个节点之间拥有一条通路,比如(a,b)表示a可以到达b,b也可以到达a.然后输入起始节点和目标节点,输出任何可能的路径.路径中不得包含回路. 输入示范 3 a,b a,c b,c a c 输出示范 abc ac 输入说明 第一行代表二元组的数量 然后是所有的二元组 第5行起始节点 第6行终止节点 用Java或者C#完成 解决方案 http://leaver.me/archives/2561.html 解决方案二: http://

求解答-求比较两个图清晰度的代码,有谢谢谢谢啦

问题描述 求比较两个图清晰度的代码,有谢谢谢谢啦 比如拍了两张照片,要比较哪一张更加清楚的代码,matlab ,c,OpenCV都可以(用灰度函数,拉普拉斯算子等) 解决方案 写个matlab算下差分,应该有个指标可以衡量一下 function out_val=difference_absolute(img);I=rgb2gray(img);[mn]=size(I);f=0.0;I=double(I);for x=1:m-1; for y=1:n-1; Ix=I(x+1y)-I(xy); Iy=