ツリー内の2つのノードの最低の共通祖先
2480 ワード
タイトルの説明:
1本の木を与え、同時に木の中の2つのノードを与えて、それらの最低の公共の祖先を求めます.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力された第1の動作の数n(0出力:
各テストケースに対応して、与えられたツリー内の2つのノードの最低共通祖先ノードの値を出力し、2つの与えられたノードに最低共通祖先がない場合は「My God」を出力します.
サンプル入力:
サンプル出力:
1本の木を与え、同時に木の中の2つのノードを与えて、それらの最低の公共の祖先を求めます.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力された第1の動作の数n(0
各テストケースに対応して、与えられたツリー内の2つのノードの最低共通祖先ノードの値を出力し、2つの与えられたノードに最低共通祖先がない場合は「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
");
continue;
}
if(!getPath(root,b,path2,top2)){
printf("My God
");
continue;
}
destory(root);
printf("%d
",getCommonNode(path1,path2));
}
}
return 0;
}