题目1509：树中两个结点的最低公共祖先

题目描述：

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

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数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<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std ;
typedef struct node
{
 int data ;
 struct node *left , *right ;
}node , *tree ;
void Init(tree &T){
 T = (node *)malloc(sizeof(node));
 T->left = T->right = NULL ;
 return ;
}

void PreorderTree(tree &T)
{
 int ch ;
 cin >> ch ;
 if(ch == 0 )
 {
  T=NULL;
  return ;
 }
 T=(node*)malloc(sizeof(node)) ;
 T->data = ch ;
 PreorderTree(T->left);
 PreorderTree(T->right);
 return ;
}

int a[1002] , b[1002]  ,  j = 0 , tag = false;
void PreorderTra(tree T , int node1 )
{
 if(T){
  if(T->data == node1){
   a[j++] = T->data ;
   tag = true ;
  }
  if(!tag){ 
  a[j++] = T->data ;
  PreorderTra(T->left , node1 ) ;
  PreorderTra(T->right , node1 );
  if(!tag)
   j-- ;
  }
  
 }
}
void PreorderTra1(tree T , int node1 )
{
 if(T){
  if(T->data == node1){
   b[j++] = T->data ;
   tag = true ;
  }
  if(!tag)
  {
  b[j++] = T->data ;
  PreorderTra1(T->left , node1 ) ;
  PreorderTra1(T->right , node1 );
  if(!tag) 
  j-- ;
  }
 }
}
int main(void)
{
 int t ;
 cin >> t ; 
 while(t --){
  tree T;
  Init(T);
  PreorderTree(T);
  int i , node1 , node2 ;
  cin >> node1 >> node2 ;
  /*if(node1 == node2){
   cout<<node1<<endl;
   continue ;
  }*/
  j = 0 ;
  tag = false; 
  PreorderTra(T , node1 );
  int ka = j ;
 /* for( i = 0 ; i < ka ; i ++)
   cout<<a[i]<<" ";
  cout<<endl; */

  j = 0 ;
  tag = false ;
  PreorderTra1(T,node2 );
  int kb = j ;
  /*for( i = 0 ; i < kb ; i ++)
   cout<<b[i]<<" ";
  cout<<endl; */
  bool flag = false ;
  for( i = ka-1 ; i >=0 ; i--){
   for( j = kb-1; j >=0 ; j--)
    if(a[i] == b[j]){
     cout<<a[i]<<endl;
     flag = true ;
     break;
    }
    if(flag)
     break;
  }
  if(!flag)
   cout<<"My God"<<endl;
  
 }
 return 0;
}