使用C語(yǔ)言求二叉樹(shù)結(jié)點(diǎn)的最低公共祖先的方法
算法分析
我們直接來(lái)分析O(n)的算法。

比如求節(jié)點(diǎn)F和節(jié)點(diǎn)H的最低公共祖先,先求出從根節(jié)點(diǎn)A到F的路徑,再求出A到H的路徑,那么最后一個(gè)相同的節(jié)點(diǎn)就是最低公共祖先。A->B->D->F和A->B->E->H,最后相同的節(jié)點(diǎn)事B,所以最低公共祖先是B節(jié)點(diǎn)。求根節(jié)點(diǎn)到指定節(jié)點(diǎn)的算法先前已經(jīng)更新過(guò)了,復(fù)雜度是O(n),所以總的時(shí)間復(fù)雜度是O(n)。
條件細(xì)化:
(1)樹(shù)如果是二叉樹(shù),而且是二叉排序樹(shù)。
這中條件下可以使用二叉排序樹(shù)的搜索功能找到最低公共祖先。
(2)樹(shù)不是二叉排序樹(shù),連二叉樹(shù)都不是,就是普通的樹(shù)。
1,如果樹(shù)中有指向父節(jié)點(diǎn)的指針。
這問(wèn)題可以將問(wèn)題轉(zhuǎn)化為兩個(gè)鏈表相交,求兩個(gè)鏈表的第一個(gè)交點(diǎn)。
2,如果樹(shù)中沒(méi)有指向父節(jié)點(diǎn)的指針。
這問(wèn)題就有點(diǎn)麻煩了。
具體來(lái)看獲取從根節(jié)點(diǎn)到指定節(jié)點(diǎn)的函數(shù)代碼:
struct BinaryNode
{
char value;
BinaryNode *left;
BinaryNode *right;
};
求跟節(jié)點(diǎn)到指定節(jié)點(diǎn)路徑:
bool GetNodePath(BinaryNode *pRoot,BinaryNode *pNode,vector<BinaryNode*> &v)
{
if(pRoot==NULL)
return false;
v.push_back(pRoot);
if(pRoot==pNode)
return true;
bool found=GetNodePath(pRoot->left,pNode,v);
if(!found)
found=GetNodePath(pRoot->right,pNode,v);
if(!found)
v.pop_back();
}
求最低公共祖先節(jié)點(diǎn):
BinaryNode* GetCommonParent(BinaryNode *pRoot,BinaryNode *pNode1,BinaryNode *pNode2)
{
if(pRoot==NULL || pNode1==NULL || pNode2==NULL)
return NULL;
vector<BinaryNode*> v1,v2;
GetNodePath(pRoot,pNode1,v1);
GetNodePath(pRoot,pNode2,v2);
BinaryNode *pLast=pRoot;
vector<BinaryNode*>::iterator ite1=v1.begin();
vector<BinaryNode*>::iterator ite2=v2.begin();
while(ite1!=v1.end() && ite2!=v2.end())
{
if(*ite1==*ite2)
pLast=*ite1;
ite1++;
ite2++;
}
return pLast;
}
來(lái)看一道具體的ACM題目
題目描述:
給定一棵樹(shù),同時(shí)給出樹(shù)中的兩個(gè)結(jié)點(diǎn),求它們的最低公共祖先。
輸入:
輸入可能包含多個(gè)測(cè)試樣例。
對(duì)于每個(gè)測(cè)試案例,輸入的第一行為一個(gè)數(shù)n(0<n<1000),代表測(cè)試樣例的個(gè)數(shù)。
其中每個(gè)測(cè)試樣例包括兩行,第一行為一個(gè)二叉樹(shù)的先序遍歷序列,其中左右子樹(shù)若為空則用0代替,其中二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)node_num<10000。
第二行為樹(shù)中的兩個(gè)結(jié)點(diǎn)的值m1與m2(0<m1,m2<10000)。
輸出:
對(duì)應(yīng)每個(gè)測(cè)試案例,
輸出給定的樹(shù)中兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)的值,若兩個(gè)給定結(jié)點(diǎn)無(wú)最低公共祖先,則輸出“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
思路
這道題我考慮的思路是
(1)后序遍歷的思想,用棧保存到查找點(diǎn)的路徑
(2)然后求兩個(gè)棧第一個(gè)公共節(jié)點(diǎn)
AC代碼
#include <stdio.h>
#include <stdlib.h>
#define N 7000
typedef struct btree {
struct btree *lchild, *rchild;
int data;
} btree;
typedef struct stack {
int top;
btree* data[N];
} stack;
stack *first, *second;
int oneflag, secflag;
/**
* 根據(jù)前序序列遞歸構(gòu)建二叉樹(shù)
*/
void createBtree(btree **t)
{
int data;
scanf("%d", &data);
if (data == 0) {
*t = NULL;
} else {
*t = (btree *)malloc(sizeof(btree));
(*t)->data = data;
createBtree(&(*t)->lchild);
createBtree(&(*t)->rchild);
}
}
/**
* 后序遍歷二叉樹(shù),構(gòu)造遍歷棧
*/
void postTraverse(btree *t, stack *s, int srcnum, int *flag)
{
if (t != NULL) {
btree *pre;
pre = NULL;
s->data[s->top ++] = t;
while (s->top > 0 || t) {
if (t) {
s->data[s->top ++] = t;
if (t->data == srcnum) {
*flag = 1;
break;
}
t = t->lchild;
} else {
t = s->data[-- s->top];
if (t->rchild == NULL || t->rchild == pre) {
pre = t;
t = NULL;
} else {
s->data[s->top ++] = t;
t = t->rchild;
}
}
}
}
}
/**
* 查找兩個(gè)棧第一個(gè)公共元素
*
* T = O(n)
*
*/
void stackCommonData(stack *f, stack *s)
{
int top, data, flag;
top = (f->top > s->top) ? s->top : f->top;
while (top > 0) {
if (f->data[top - 1]->data == s->data[top - 1]->data) {
data = f->data[top - 1]->data;
flag = 1;
break;
} else {
top --;
}
}
if (flag) {
printf("%d\n", data);
} else {
printf("My God\n");
}
}
/**
* 清理二叉樹(shù)
*
*/
void cleanBtree(btree *t)
{
if (t) {
cleanBtree(t->lchild);
cleanBtree(t->rchild);
free(t);
}
}
int main(void)
{
int n, sf, se;
btree *t;
scanf("%d", &n);
while (n --) {
createBtree(&t);
scanf("%d %d", &sf, &se);
first = (stack *)malloc(sizeof(stack));
first->top = 0;
oneflag = 0;
postTraverse(t, first, sf, &oneflag);
second = (stack *)malloc(sizeof(stack));
second->top = 0;
secflag = 0;
postTraverse(t, second, se, &secflag);
if (oneflag == 0 || secflag == 0 || first->top == 0 || second->top == 0) {
printf("My God\n");
cleanBtree(t);
continue;
} else {
stackCommonData(first, second);
cleanBtree(t);
}
}
return 0;
}
/**************************************************************
Problem: 1509
User: wangzhengyi
Language: C
Result: Accepted
Time:150 ms
Memory:110212 kb
****************************************************************/
- C語(yǔ)言判定一棵二叉樹(shù)是否為二叉搜索樹(shù)的方法分析
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法示例
- c語(yǔ)言_構(gòu)建一個(gè)靜態(tài)二叉樹(shù)實(shí)現(xiàn)方法
- 使用C語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)求解的簡(jiǎn)單方法
- C語(yǔ)言實(shí)現(xiàn)找出二叉樹(shù)中某個(gè)值的所有路徑的方法
- C語(yǔ)言實(shí)現(xiàn)計(jì)算樹(shù)的深度的方法
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列之樹(shù)的概念結(jié)構(gòu)和常見(jiàn)表示方法
相關(guān)文章
C語(yǔ)言關(guān)于二叉樹(shù)中堆的創(chuàng)建和使用整理
大家好,這里是針對(duì)二叉樹(shù)中堆結(jié)構(gòu)的順序儲(chǔ)存,整理出來(lái)一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們?cè)谠u(píng)論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步2022-08-08
cmake添加一個(gè)庫(kù)的實(shí)現(xiàn)步驟
本文主要介紹了cmake添加一個(gè)庫(kù)的實(shí)現(xiàn)步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
VS2022配置編譯使用boost庫(kù)的實(shí)現(xiàn)
本文介紹了如何在VS2022中配置和編譯使用Boost庫(kù)的步驟,包括下載Boost、解壓、配置環(huán)境變量和編譯等過(guò)程,具有一定的參考價(jià)值,感興趣的可以了解一下2024-12-12
C++中圖片類型的識(shí)別與轉(zhuǎn)換詳解方法
本文簡(jiǎn)單的介紹一下C++語(yǔ)言中如何識(shí)別圖片文件的類型,以及各圖片類型之間的轉(zhuǎn)換方法,并提供相關(guān)的源碼供大家參考,感興趣的朋友快來(lái)看看吧2021-11-11
C++超詳細(xì)講解內(nèi)存空間分配與this指針
this?指針在C++類和對(duì)象中是個(gè)很方便實(shí)用的關(guān)鍵字,可以簡(jiǎn)化對(duì)象成員屬性的調(diào)用,使代碼表達(dá)的含義更加準(zhǔn)確;在之前的學(xué)習(xí)中我們都可以判斷變量所占內(nèi)存空間大小,那么我們創(chuàng)建的類對(duì)象所占的內(nèi)存空間怎么計(jì)算呢?想知道this的妙用和類對(duì)象占用的內(nèi)存空間就來(lái)跟我學(xué)習(xí)吧2022-05-05
有關(guān)C++中類類型轉(zhuǎn)換操作符總結(jié)(必看篇)
下面小編就為大家?guī)?lái)一篇有關(guān)C++中類類型轉(zhuǎn)換操作符總結(jié)(必看篇)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
深入了解C語(yǔ)言中的字符串和內(nèi)存函數(shù)
本文主要帶大家來(lái)學(xué)習(xí)一些常用的庫(kù)函數(shù)。有了這些庫(kù)函數(shù),我們可以更加方便地操作字符串和內(nèi)存,從而提升我們的編碼效率。話不多說(shuō),我們開(kāi)始吧2022-11-11

