PATA-1151 LCA in a Binary Tree

题意：根据前序和中序建立树，寻找两个点的LCA。

我在之前的博客中写了关于LCA的多种求法。 https://www.cnblogs.com/yy-1046741080/p/11505547.html。在建树的过程中，建立深度和parent，来寻找LCA。

该题目的数据有一定的欺诈性，它给你结点数据是1-8，如果没有仔细看清题目，那么很有可能定义一个 node tree[10005]的数组，但是题目并没有说数据范围在1-10000内。

经过测试，如果你将范围定义稍微大一点，还是能全过的；

我在这里采用的就是二叉链表，使用二叉链表麻烦的一点在于，需要查找u，v两个结点，返回其指针。

我认为最好的方法就是建立一个映射表，映射输入data和node tree[]中下标的关系，就不需要进行查找。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 struct node {
  5     int data;
  6     struct node* left, * right;  //left/right=-1,表示空子树
  7     int depth;
  8     struct node* parent;
  9 };
 10 
 11 node* root;  // 树的根
 12 int pre[10005];  // 先序遍历序列
 13 int in[10005];  // 后序遍历序列
 14 set<int> is_visit;
 15 
 16 // 先序序列pre[preL,preR],中序序列in[inL,inR],    depth/parent:for LCA;
 17 node* BuildTree(int preL, int preR, int inL, int inR, int depth, node* parent) {
 18     if (preL > preR) {
 19         return NULL;
 20     }
 21     node* root = new node;
 22     root->data = pre[preL];
 23     root->depth = depth;
 24     root->parent = parent;
 25     int k;
 26     for (k = inL; in[k] != pre[preL]; k++) {
 27         ;
 28     }
 29     root->left = BuildTree(preL + 1, preL + k - inL, inL, k - 1, depth + 1, root);
 30     root->right = BuildTree(preL + k - inL + 1, preR, k + 1, inR, depth + 1, root);
 31 
 32     return root; // 返回
 33 }
 34 
 35 // 寻找权值为value的结点
 36 void find(node* root, int value,node* &t) {
 37     if (root != NULL) {
 38         if (root->data == value) {
 39             t = root;
 40         }
 41         else {
 42             find(root->left, value,t);
 43             find(root->right, value,t);
 44         }
 45     }
 46 }
 47 
 48 int LCA(int u, int v) {
 49     node* uu;
 50     find(root, u, uu);
 51     node* vv;
 52     find(root, v, vv);
 53     while (uu->depth > vv->depth) {
 54         uu = uu->parent;
 55     }
 56     while (uu->depth < vv->depth) {
 57         vv = vv->parent;
 58     }
 59     while (uu != vv) {
 60         uu = uu->parent;
 61         vv = vv->parent;
 62     }
 63     return uu->data;
 64 }
 65 
 66 int main() {
 67     int N, M;
 68     cin.sync_with_stdio(false);
 69     cin >> N >> M;
 70     for (int i = 1; i <= M; i++) {
 71         cin >> in[i];
 72         is_visit.insert(in[i]);
 73     }
 74     for (int i = 1; i <= M; i++) {
 75         cin >> pre[i];
 76     }
 77     root = BuildTree(1, M, 1, M, 1, NULL);
 78     while (N--) {
 79         int u, v;
 80         cin >> u >> v;
 81         bool f1 = is_visit.find(u) != is_visit.end() ? true : false;
 82         bool f2 = is_visit.find(v) != is_visit.end() ? true : false;
 83 
 84         if (!f1 && !f2) {
 85             cout << "ERROR: " << u << " and " << v << " are not found.
";
 86         }
 87         else if (!f1) {
 88             cout << "ERROR: " << u <<" is not found.
";
 89         }
 90         else if (!f2) {
 91             cout << "ERROR: " << v <<" is not found.
";
 92         }
 93         else {
 94             int w = LCA(u, v);
 95             if (w == u) {
 96                 cout << u << " is an ancestor of " << v << ".
";
 97             }
 98             else if (w == v) {
 99                 cout << v << " is an ancestor of " << u << ".
";
100             }
101             else {
102                 cout << "LCA of " << u << " and " << v << " is " << w << ".
";
103             }
104         }
105     }
106 }