题目描述：
-
给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。
输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数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
【解题思路】首先是树的输入，这个利用中序遍历的特点递归输入就行。然后，我们需要判断给出的两个节点是否都在树中，不在直接输出非法信息。若都在树中则继续查找，这个时候我们需要递归查找，给定一个头节点和两个待查的节点值，首先判断如果节点值等于头结点的节点值，那么公共节点肯定就是头节点；否则，继续在头结点的左支和右支中间查找，若两个节点值分居左右支树中，那么公共节点肯定也就是头结点。否则我们可以通过左支或者右支返回的节点得到公共节点。
注意根节点需要通过传地址调用才能返回值，所以create参数是指针的指针。
AC code:
#include <cstdio>
#include <set>
using namespace std;
struct nod
{
int val;
nod *lc,*rc;
};
set<int> setin;
void create(nod **nd)
{
int tt;
scanf("%d",&tt);
if(tt==0) {nd=NULL; return;}
else
{
setin.insert(tt);
nod *newnd=new nod();
newnd->val=tt;
*nd=newnd;
create(&(newnd->lc));
create(&(newnd->rc));
}
}
nod * lca(nod *nd,const int &n,const int &m)
{
if(!nd) return NULL;
if(nd->val==n || nd->val==m) return nd;
nod *lnd=lca(nd->lc,n,m);
nod *rnd=lca(nd->rc,n,m);
if(lnd && rnd) return nd;
return lnd?lnd:rnd;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
nod *head=NULL;
setin.clear();
create(&head);
int n,m;
scanf("%d%d",&n,&m);
if(setin.find(n)==setin.end() || setin.find(m)==setin.end())
{
printf("My God\n");
continue;
}
nod *re=lca(head,n,m);
printf("%d\n",re->val);
}
return 0;
}
/**************************************************************
Problem: 1509
User: huo_yao
Language: C++
Result: Accepted
Time:160 ms
Memory:4988 kb
****************************************************************/
题目链接：http://ac.jobdu.com/problem.php?pid=1509九度-剑指Offer习题全套答案下载：http://download.csdn.net/detail/huoyaotl123/8276299
| 
转播
