树中两个结点的最低公共祖先

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

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

#include <cstdio>
#include <iostream>
#include <list>
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;	
}

补充：软件开发 , C++ ,

上一个：题目描述：字符串查找
下一个：骑士问题