題目描述：

給定一棵樹，同時給出樹中的兩個結點，求它們的最低公共祖先。

輸入：

輸入可能包含多個測試樣例。
對于每個測試案例，輸入的第一行為一個數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; }

?

?

轉載于:https://www.cnblogs.com/snake-hand/p/3170135.html

總結

以上是生活随笔為你收集整理的树中两个结点的最低公共祖先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。