1151 LCA in a Binary Tree (30分)

自己写的：

先建树，然后利用后续非递归遍历求解

#include<iostream>
#include<stack>
using namespace std;
const int maxn = 10010;
typedef struct node {
    int n;node* left;node* right;
}*tree;
int n, m, pre[maxn], in[maxn];
tree createT(int preS, int preE, int inS, int inE) {
    if (preS > preE)return NULL;tree root = new node;root->n = pre[preS];int pos = inS;for (int i = inS; i <= inE; i++) {
    if (in[i] == pre[preS]) {
    pos = i;break;}}int length = pos - inS;root->left = createT(preS + 1, preS + length, inS, pos - 1);root->right = createT(preS + length + 1, preE, pos + 1, inE);return root;
}
int getAns(int u, int v, tree t) {
    tree stack[maxn], temp[maxn];int top = -1, tempTop = -1;tree p = t, pre = NULL;while (p != NULL || top != -1) {
    while (p != NULL) {
    stack[++top] = p;p = p->left;}if (top != -1) {
    p = stack[top];if (p->right != NULL && p->right != pre) {
    p = p->right;}else {
    if ((p->n == u) || (p->n == v)) {
    if (tempTop == -1) {
    for (int i = 0; i <= top; i++) {
    tempTop++;temp[tempTop] = stack[tempTop];}}else {
    int length = (top < tempTop) ? top : tempTop;for (int i = length; i >= 0; i--) {
    if (stack[i]->n == temp[i]->n) {
    return stack[i]->n;}}}}top--;pre = p;p = NULL;}}}
}
int main() {
    cin >> m >> n;for (int i = 0; i < n; i++)cin >> in[i];for (int i = 0; i < n; i++)cin >> pre[i];tree t = createT(0, n - 1, 0, n - 1);for (int i = 0; i < m; i++) {
    int u, v;cin >> u >> v;bool findu = false, findv = false;for (int j = 0; j < n; j++) {
    if (pre[j] == u)findu = true;if (pre[j] == v)findv = true;}if (findu == false && findv == false) {
    printf("ERROR: %d and %d are not found.\n", u, v);continue;}if (findu == false) {
    printf("ERROR: %d is not found.\n", u);continue;}if (findv == false) {
    printf("ERROR: %d is not found.\n", v);continue;}int ans = getAns(u, v, t);if (u == v) {
    printf("%d is an ancestor of %d.\n", u, v);continue;}if (ans != u && ans != v) {
    printf("LCA of %d and %d is %d.\n", u, v, ans);continue;}if (ans == u) {
    printf("%d is an ancestor of %d.\n", u, v);continue;}if (ans == v) {
    printf("%d is an ancestor of %d.\n", v, u);continue;}}
}

看了大佬答案后写的：

PAT 1151 LCA in a Binary Tree（30 分）- 甲级
不需要建树，在中序序列中，如果u和v的位置在当前节点root的位置的左边，则lca在root的左子树中，如果u和v的位置在当前节点root的位置的右边，则lca在root的右子树中，否则，u和v在root两侧，那么root就是lca。
关键在于记录每个节点在中序序列中的位置。

#include<iostream>
#include<map>
using namespace std;
const int maxn = 1010;
int pre[maxn], in[maxn], m, n;
map<int, int>pos;//记录各个节点在中序序列中的位置void lca(int inS, int inE, int root, int u, int v) {
    //root是中序序列中[inS，inE]这一部分子树的根//在先序序列中的位置if (inS > inE)return;int rootPos = pos[pre[root]];//求## 标题子树根在中序序列中的位置int uPos = pos[u];int vPos = pos[v];if (uPos < rootPos && vPos < rootPos)lca(inS, rootPos - 1, root + 1, u, v);else if (uPos > rootPos&& vPos > rootPos)lca(rootPos + 1, inE, root + rootPos - inS + 1, u, v);else if ((uPos<rootPos && vPos>rootPos) || (uPos > rootPos&& vPos < rootPos))printf("LCA of %d and %d is %d.\n", u, v, pre[root]);else if (uPos == rootPos)printf("%d is an ancestor of %d.\n", u, v);else if (vPos == rootPos) {
    printf("%d is an ancestor of %d.\n", v, u);}
}
int main() {
    cin >> m >> n;for (int i = 1; i <= n; i++) {
    cin >> in[i];pos[in[i]] = i;}for (int i = 1; i <= n; i++)cin >> pre[i];for (int i = 0; i < m; i++) {
    int u, v;cin >> u >> v;if (pos.count(u) == 0 && pos.count(v) == 0)printf("ERROR: %d and %d are not found.\n", u, v);else if (pos.count(u) == 0 || pos.count(v) == 0)printf("ERROR: %d is not found.\n", pos.count(u) == 0 ? u : v);elselca(1, n, 1, u, v);}return 0;
}

注意：u和v相等且都在树中时，输出格式是：u is an ancestor of u.而不是LCA of u and u is u.这里写错会导致第二个测点不通过

递归求LCA，还是比较容易理解的。
（二叉树）二叉树的最近公共祖先

tree lca(tree root, tree p, tree q) {
    //这里假设p和q都在树上if(root==p||root==q||!root)return root;tree left=lca(root->left,  p, q);tree right=lca(root->right,  p, q);    if(!left&&!right)return NULL;//左右子树都没有找到p和qelse if(left&&!right)return left;//。。。else if(right&&!left)return right; //。。。else							//p和q分属左右子树的情况return root;}

我好菜呀