如何制作网站连接数据库,重庆市建设工程信息网查询人员,做公众号网站有哪些,如何开网店做电商题意#xff1a;
给定前序遍历和中序遍历#xff0c;问u和v的lca #xff08;先是中序#xff0c;后是中序#xff09;
题解#xff1a;
方法一#xff1a;
参考题解 将树映射到一颗BST上#xff0c;在BST上找到答案然后再映射回原本的树 方法二#xff1a; 参考题…题意
给定前序遍历和中序遍历问u和v的lca 先是中序后是中序
题解
方法一
参考题解 将树映射到一颗BST上在BST上找到答案然后再映射回原本的树 方法二 参考题解 已知某个树的根结点若a和b在根结点的左边则a和b的最近公共祖先在当前子树根结点的左子树寻找如果a和b在当前子树根结点的两边在当前子树的根结点就是a和b的最近公共祖先如果a和b在当前子树根结点的右边则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树在不构建树的情况下在每一层的递归中可以得到树的根结点在此时并入lca算法可以确定两个结点的公共祖先
代码
#include iostream
#include vector
#include set
#include cstring
#include cstdio
#include mapusing namespace std;int m, n;
int opre[10009], oin[10009];
int pre[10009], in[10009];
mapint, int otos, stoo;int main()
{cin m n;for (int i 0; i n; i){cin oin[i];otos[oin[i]] i;stoo[i] oin[i];}for (int i 0; i n; i){cin opre[i];pre[i] otos[opre[i]];}for (int i 0; i m; i){int u, v;int a;bool flag1 true, flag2 true;cin u v;if (otos.find(u) otos.end())flag1 false;if (otos.find(v) otos.end())flag2 false;if (!flag1 || !flag2){if (!flag1 !flag2)printf(ERROR: %d and %d are not found.\n, u, v);elseprintf(ERROR: %d is not found.\n, flag1 false ? u : v);continue;}u otos[u];v otos[v];for (int j 0; j n; j){a pre[j];if (a u a v || a u a v || a u || a v)break;}u stoo[u];v stoo[v];a stoo[a];if (a u || a v)printf(%d is an ancestor of %d.\n, a, a u ? v : u);elseprintf(LCA of %d and %d is %d.\n, u, v, a);}return 0;
}#include iostream
#include vector
#include map
using namespace std;
mapint, int pos;
vectorint in, pre;
void lca(int inl, int inr, int preRoot, int a, int b) {if (inl inr) return;int inRoot pos[pre[preRoot]], aIn pos[a], bIn pos[b];if (aIn inRoot bIn inRoot)lca(inl, inRoot-1, preRoot1, a, b);else if ((aIn inRoot bIn inRoot) || (aIn inRoot bIn inRoot))printf(LCA of %d and %d is %d.\n, a, b, in[inRoot]);else if (aIn inRoot bIn inRoot)lca(inRoot1, inr, preRoot1(inRoot-inl), a, b);else if (aIn inRoot)printf(%d is an ancestor of %d.\n, a, b);else if (bIn inRoot)printf(%d is an ancestor of %d.\n, b, a);
}
int main() {int m, n, a, b;scanf(%d %d, m, n);in.resize(n 1), pre.resize(n 1);for (int i 1; i n; i) {scanf(%d, in[i]);pos[in[i]] i;}for (int i 1; i n; i) scanf(%d, pre[i]);for (int i 0; i m; i) {scanf(%d %d, a, b);if (pos[a] 0 pos[b] 0)printf(ERROR: %d and %d are not found.\n, a, b);else if (pos[a] 0 || pos[b] 0)printf(ERROR: %d is not found.\n, pos[a] 0 ? a : b);elselca(1, n, 1, a, b);}return 0;
}
