- 题目描述：
-
给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。 其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num<10000。 第二行为树中的两个结点的值m1与m2(0<m1,m2<10000)。
- 输出：
-
对应每个测试案例，
输出给定的树中两个结点的最低公共祖先结点的值，若两个给定结点无最低公共祖先，则输出“My God”。
- 样例输入：
-
21 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 06 81 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 06 12
- 样例输出：
-
2My God
#include#include #include using namespace std;struct Node{ int x; struct Node *left; struct Node *right;};int path1[10000],path2[10000];int top1 = -1,top2 = -1;void createTree(Node *&root){ int x; scanf("%d",&x); if(!x) root = NULL; else{ root = new Node; root->x = x; createTree(root->left); createTree(root->right); }}bool getPath(Node *root,int x,int path[],int &top){ path[++top] = root->x; if(root->x == x) return true; bool found = false; if(root->left) found = getPath(root->left,x,path,top); if(!found && root->right) found = getPath(root->right,x,path,top); if(!found) top--; return found;}int getCommonNode(int path1[],int path2[]){ int x; int i = 0,j = 0; while(i <= top1 && j <= top2){ if(path1[i] == path2[j]) x = path1[i]; i++;j++; } return x;}void destory(Node *&root){ if(root){ destory(root->left); destory(root->right); delete root; root = NULL; }}void print(Node *root){ if(root){ printf("%d ",root->x); print(root->left); print(root->right); }}int main(int argc, char const *argv[]){ int n,a,b; while(scanf("%d",&n) != EOF){ while(n--){ Node *root; createTree(root); scanf("%d %d",&a,&b); top1 = -1;top2 = -1; if(!getPath(root,a,path1,top1)){ printf("My God\n"); continue; } if(!getPath(root,b,path2,top2)){ printf("My God\n"); continue; } destory(root); printf("%d\n",getCommonNode(path1,path2)); } } return 0; }