二叉树的最近公共祖先（设计一个算法求出指定节点在二叉树中的层次）

算法分析

我们直接来分析O(n)的算法。

比如求节点F和节点H的最低公共祖先，先求出从根节点A到F的路径，再求出A到H的路径，那么最后一个相同的节点就是最低公共祖先。A->B->D->F和A->B->E->H，最后相同的节点事B，所以最低公共祖先是B节点。求根节点到指定节点的算法先前已经更新过了，复杂度是O(n)，所以总的时间复杂度是O(n)。
条件细化：
(1)树如果是二叉树，而且是二叉排序树。
这中条件下可以使用二叉排序树的搜索功能找到最低公共祖先。
(2)树不是二叉排序树，连二叉树都不是，就是普通的树。
1，如果树中有指向父节点的指针。
这问题可以将问题转化为两个链表相交，求两个链表的第一个交点。
2，如果树中没有指向父节点的指针。
这问题就有点麻烦了。


具体来看获取从根节点到指定节点的函数代码：

?

1 2 3 4 5 6

struct BinaryNode { char value; BinaryNode *left; BinaryNode *right; };

求跟节点到指定节点路径：

?

1 2 3 4 5 6 7 8 9 10 11 12 13

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(); }

求最低公共祖先节点：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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; }

来看一道具体的ACM题目

题目描述：
给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。

输入：
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数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

思路
这道题我考虑的思路是

(1)后序遍历的思想,用栈保存到查找点的路径
(2)然后求两个栈第一个公共节点

AC代码

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

#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; /** * 根据前序序列递归构建二叉树 */ 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); } } /** * 后序遍历二叉树,构造遍历栈 */ 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; } } } } } /** * 查找两个栈第一个公共元素 * * 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"); } } /** * 清理二叉树 * */ 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
****************************************************************/