题目描述：
给出一颗二叉树的后序遍历和中序遍历，你能计算出两个结点的最近公共祖先吗？
输入格式:
第一行给出两个整数N(N<=10000)和M(M<=10000)，分别代表二叉树的结点数和我们接下来的询问数。
第二行和第三行分别给出N个整数，每个整数用空格分开，分别代表二叉树的后序遍历和中序遍历。
接下来M行，每行给出两个整数，代表我们要询问的两个结点的编号a和b。
输出格式:
对于每个我们要求的询问：
1.如果a和b中有一个或两个不在树上，输出"ERROR"。
2.否则在一行中输出一个整数，表示a和b的最近公共祖先。
输入样例:
在这里给出一组输入。例如：
3 3 2 3 1 2 1 3 1 2 2 3 0 3
输出样例:
在这里给出相应的输出。例如：
1 1 ERROR
先讲一下思路：这道题最主要的还是怎么去查找这个公共祖先的问题， 建树不是主要的。首先应该把树建好。接下来是查找
1、查找的时候，找到我们要找的结点就直接返回
2、找不到的就返回NULL
3、查找到最后，返回的是它两的公共祖先
#include<bits/stdc++.h> using namespace std;// typedef struct node { int num ; struct node * left; struct node * right; }Node; vector<int> vec; queue<Node*> q; Node * build(int *zhong , int * hou , int n)/// 建树 { Node *tree; if(zhong==NULL || hou == NULL || n <= 0) return NULL; int gen = *(hou+n-1); int k = 0; while(*zhong != gen){/// 前序遍历和中序遍历 zhong++; k++; } tree = (Node*)malloc(sizeof(node)); tree->num = gen ; tree->left = build(zhong-k , hou , k); tree->right = build(zhong+1 , hou+k , n-k-1); return tree; } Node* solve(Node * tree , int a , int b )/// 查找最近的公共祖先 { if (tree == NULL) /// 树NULL ， 说明没有找到这个结点 return NULL; if(a == tree->num || b == tree->num)/// 当前的这个结点就是要找的结点之一 return tree; Node *t = NULL; Node *left_ = solve(tree->left ,a , b);/// 左右子树找 Node * right_ = solve(tree->right , a ,b); if(left_ && right_)/// 一个在左子树，一个在右子树 ， 说明当前的结点就是最近的公共祖先了 return tree; if(left_ == NULL)/// return right_; else return left_; } int main() { int n , m; cin>>n>>m; int zhong[10001] , hou[10001]; bool flog[10001];/// 标记数组，这个数字出现过了，就 true for(int i = 0; i < n ; i++){ cin>>hou[i]; flog[hou[i]] = true; } for(int i = 0; i < n ; i++) cin>>zhong[i]; Node *tree = build(zhong , hou , n);/// 建树 vec.push_back(0); for(int i = 0 ; i < m ; i++){ int a , b ; cin>>a>>b; if(!flog[a] || !flog[b]){/// 看这个结点有没有，没有就直接continue了 cout<<"ERROR"<<endl; continue; } Node * t = solve(tree , a,b);/// 找 a , b 的最近祖先 ， 返回的是最近祖先的结点node cout<<t->num<<endl;/// } return 0; } /* 3 2 2 3 1 2 1 3 1 2 2 3 */