剑指Offer - 九度1509 - 树中两个结点的最低公共祖先
2014-02-07 01:04
- 题目描述：
-
给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数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
题意分析：
这道题要求将二叉搜索树转换成双向链表，我的思路是进行后序遍历。先将左右子树搞定以后，再处理根节点。
求最近公共父节点的常用方法，有Tarjan离线算法，在线倍增法，Naive算法。
目前我只写了Naive算法和在线倍增法的代码，结果提交后发现Naive算法通过，倍增法始终Wrong Answer。
检查代码许久，开始怀疑数据有问题，于是在两处设置了死循环的测试代码，提交结果中果然有两处问题：
1. 查询的节点值可能为0，也就是代表NULL的0。这个我倒是可以处理好。
2. 二叉树中的节点值是可能有重复的，比如值为5的节点可以有很多个，那么输入5的话让我找哪个？推测倍增法出错和这个有关。
由于这题数据有问题，所以没有继续写Tarjan版本的欲望了，很可能也AC不掉。我会在Leetcode中的对应题目附上三种方法的讲解，此处就不做详述了。
Naive算法时间复杂度O(h)，其中h为二叉树的高度，平均为O(log(n))，对于斜树来说则是O(n)。
倍增法则用O(n * log(n))空间复杂度和O(n * log(n))预处理时间，来获取O(log(n))的稳定查询复杂度。
// 690809 zhuli19901106 1509 Accepted 点击此处查看所有case的执行结果 1176KB 6753B 120MS
// 201402050235
// This solution is Naive Algorithm, may fail on very large skewed tree.
// If you optimize it with ancestor array to achieve O(log(n)) time, you'll get WA.
// Because the test data of this problem have some illegal input.
#include <cstdio>
#include <cstring>
using namespace std; const int MAXN = ;
// tree[x][0]: parent of node x
// tree[x][1]: left child of node x
// tree[x][2]: right child of node x
// tree[x][3]: value of node x
int tree[MAXN][];
// number of nodes
int e; void build(int a)
{
int tmp; scanf("%d", &tmp);
if(tmp)
{
tree[a][] = e;
tree[e][] = tmp;
tree[e][] = a;
++e;
// build the left subtree
build(e - );
} scanf("%d", &tmp);
if(tmp)
{
tree[a][] = e;
tree[e][] = tmp;
tree[e][] = a;
++e;
// build the right subtree
build(e - );
}
}
int main()
{
int n, ni;
int i;
// the value to be queried
int m1, m2;
// the corresponding node indices of m1 and m2
int s1, s2;
int t1, t2;
int c1, c2, c; while (scanf("%d", &n) == ) {
for (ni = ; ni < n; ++ni) {
// get value for root node
e = ;
scanf("%d", &tree[][]); // root has no parent node
tree[][] = -;
build(); scanf("%d%d", &m1, &m2);
s1 = s2 = -;
for (i = ;i <= e; ++i) {
if (tree[i][] == m1) {
s1 = i;
// there're duplicate values
break;
}
}
for (i = ;i <= e; ++i) {
if (tree[i][] == m2) {
s2 = i;
// there're duplicate values
break;
}
} if (s1 != - && s2 != -) {
t1 = s1;
t2 = s2;
c1 = c2 = ; // c1 is the depth of t1
while (tree[t1][] != -) {
++c1;
t1 = tree[t1][];
}
// c2 is the depth of t2
while (tree[t2][] != -) {
++c2;
t2 = tree[t2][];
}
// move'em to the same height level
if (c1 > c2) {
c = c1 - c2;
while(c--) {
s1 = tree[s1][];
}
}
if (c2 > c1) {
c = c2 - c1;
while(c--) {
s2 = tree[s2][];
}
}
while(s1 != s2)
{
s1 = tree[s1][];
s2 = tree[s2][];
}
printf("%d\n", tree[s1][]);
} else {
// At least one value is not found in the tree.
printf("My God\n");
}
}
} return ;
} /*
// This here is my last version of code, got some strange WAs.
// I doubt if the test data is really legal as described.
// 1. m1 and m2 may be 0
// 2. some tree nodes may have same values, making things ambiguous.
// I'll prove my suspicion.
#include <cstdio>
#include <cstring>
using namespace std; typedef struct st{
public:
int key;
st *ll;
st *rr;
st(int _key = 0): key(_key), ll(NULL), rr(NULL) {}
}st; // maximal number of nodes
const int MAXN = 10005;
// key -> node_index mapping
int hash_key[MAXN];
// node_index -> key mapping
int key_hash[MAXN];
// depth of each node
int depth[MAXN];
// array recording ancestors
int anc[MAXN][16];
// total number of nodes, index starting from 1
int nc; // recursively calculate depths of nodes
void getDepth(st *root, int dep)
{
if (root == NULL) {
return;
}
depth[hash_key[root->key]] = dep;
if (root->ll != NULL) {
getDepth(root->ll, dep + 1);
}
if (root->rr != NULL) {
getDepth(root->rr, dep + 1);
}
} // recursively construct a binary tree
void constructBinaryTree(st *&root)
{
int tmp; scanf("%d", &tmp);
if (tmp == 0) {
root = NULL;
} else {
root = new st(tmp);
++nc;
if (hash_key[tmp] == 0) {
hash_key[tmp] = nc;
}
key_hash[nc] = tmp;
constructBinaryTree(root->ll);
constructBinaryTree(root->rr);
}
} // recursively initialize ancestor array
void getParent(st *root)
{
if (root == NULL) {
return;
} // anc[x][0] is the direct parent of x.
if (root->ll != NULL) {
anc[hash_key[root->ll->key]][0] = hash_key[root->key];
getParent(root->ll);
}
if (root->rr != NULL) {
anc[hash_key[root->rr->key]][0] = hash_key[root->key];
getParent(root->rr);
}
} // calculate LCA in O(log(n)) time
int leastCommonAncestor(int x, int y)
{
int i; if (depth[x] < depth[y]) {
return leastCommonAncestor(y, x);
}
for (i = 15; i >= 0; --i) {
if (depth[anc[x][i]] >= depth[y]) {
x = anc[x][i];
if (depth[x] == depth[y]) {
break;
}
}
}
if (x == y) {
return x;
} for (i = 15; i >= 0; --i) {
if (anc[x][i] != anc[y][i]) {
// they'll finally be equal, think about the reason.
x = anc[x][i];
y = anc[y][i];
}
} // this is the direct parent of x
return anc[x][0];
} st *deleteTree(st *root)
{
if (NULL == root) {
return NULL;
} if (root->ll != NULL) {
root->ll = deleteTree(root->ll);
}
if (root->rr != NULL) {
root->rr = deleteTree(root->rr);
}
delete root;
root = NULL; return NULL;
} int main()
{
int ci, cc;
int i, j;
int x, y;
st *root; while (scanf("%d", &cc) == 1) {
for (ci = 0; ci < cc; ++ci) {
// data initialization
memset(hash_key, 0, MAXN * sizeof(int));
memset(key_hash, 0, MAXN * sizeof(int));
memset(depth, 0, MAXN * sizeof(int));
memset(anc, 0, MAXN * 16 * sizeof(int));
nc = 0;
root = NULL; constructBinaryTree(root);
getParent(root);
getDepth(root, 1);
for (j = 1; j < 16; ++j) {
for (i = 1; i <= nc; ++i) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
}
scanf("%d%d", &x, &y);
if (hash_key[x] == 0 || hash_key[y] == 0) {
printf("My God\n");
} else {
printf("%d\n", key_hash[leastCommonAncestor(hash_key[x], hash_key[y])]);
} root = deleteTree(root);
}
} return 0;
}
*/