《Cracking the Coding Interview》——第4章：树和图—

《Cracking the Coding Interview》——第4章：树和图——题目7

2014-03-19 04:48

题目：最近公共父节点问题。

解法1：Naive算法，先对其高度，然后一层一层往上直到找到结果。

代码：

  1 // 4.7 Least Common Ancestor
  2 // This solution is Naive Algorithm, may timeout on very large and skewed trees.
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 const int MAXN = 10005;
  8 // tree[x][0]: parent of node x
  9 // tree[x][1]: left child of node x
 10 // tree[x][2]: right child of node x
 11 // tree[x][3]: value of node x
 12 int tree[MAXN][4];
 13 // number of nodes
 14 int e;
 15 
 16 void build(int a)
 17 {
 18     int tmp;
 19 
 20     scanf("%d", &tmp);
 21     if(tmp)
 22     {
 23         tree[a][1] = e;
 24         tree[e][3] = tmp;
 25         tree[e][0] = a;
 26         ++e;
 27         // build the left subtree
 28         build(e - 1);
 29     }
 30 
 31     scanf("%d", &tmp);
 32     if(tmp)
 33     {
 34         tree[a][2] = e;
 35         tree[e][3] = tmp;
 36         tree[e][0] = a;
 37         ++e;
 38         // build the right subtree
 39         build(e - 1);
 40     }
 41 }
 42 
 43 int main()
 44 {
 45     int n, ni;
 46     int i;
 47     // the value to be queried
 48     int m1, m2;
 49     // the corresponding node indices of m1 and m2
 50     int s1, s2;
 51     int t1, t2;
 52     int c1, c2, c;
 53 
 54     while (scanf("%d", &n)  == 1) {
 55         for (ni = 0; ni < n; ++ni) {
 56             // get value for root node
 57             e = 1;
 58             scanf("%d", &tree[0][3]);
 59 
 60             // root has no parent node
 61             tree[0][0] = -1;
 62             build(0);
 63 
 64             while (scanf("%d%d", &m1, &m2) == 2 && (m1 && m2)) {
 65                 s1 = s2 = -1;
 66                 for (i = 0;i <= e; ++i) {
 67                     if (tree[i][3] == m1) {
 68                         s1 = i;
 69                         // there're duplicate values
 70                         break;
 71                     }
 72                 }
 73                 for (i = 0;i <= e; ++i) {
 74                     if (tree[i][3] == m2) {
 75                         s2 = i;
 76                         // there're duplicate values
 77                         break;
 78                     }
 79                 }
 80 
 81                 if (s1 != -1 && s2 != -1) {
 82                     t1 = s1;
 83                     t2 = s2;
 84                     c1 = c2 = 0;
 85 
 86                     // c1 is the depth of t1
 87                     while (tree[t1][0] != -1) {
 88                         ++c1;
 89                         t1 = tree[t1][0];
 90                     }
 91                     // c2 is the depth of t2
 92                     while (tree[t2][0] != -1) {
 93                         ++c2;
 94                         t2 = tree[t2][0];
 95                     }
 96                 
 97                     // move'em to the same height level
 98                     if (c1 > c2) {
 99                         c = c1 - c2;
100                         while(c--) {
101                             s1 = tree[s1][0];
102                         }
103                     } else {
104                         c = c2 - c1;
105                         while(c--) {
106                             s2 = tree[s2][0];
107                         }
108                     }
109                 
110                     while(s1 != s2)
111                     {
112                         s1 = tree[s1][0];
113                         s2 = tree[s2][0];
114                     }
115                     printf("%d
", tree[s1][3]);
116                 } else {
117                     // At least one value is not found in the tree.
118                     printf("Not found in the tree.
");
119                 }
120             }
121         }
122     }
123 
124     return 0;
125 }

解法2：Naive算法的倍增优化。

代码：

  1 // 4.7 Least Common Ancestor
  2 // O(log(n)) solution with binary decomposition.
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 typedef struct st{
  8 public:
  9     int key;
 10     st *ll;
 11     st *rr;
 12     st(int _key = 0): key(_key), ll(NULL), rr(NULL) {}
 13 }st;
 14 
 15 // maximal number of nodes
 16 const int MAXN = 10005;
 17 // key -> node_index mapping
 18 int hash_key[MAXN];
 19 // node_index -> key mapping
 20 int key_hash[MAXN];
 21 // depth of each node
 22 int depth[MAXN];
 23 // array recording ancestors
 24 int anc[MAXN][16];
 25 // total number of nodes, index starting from 1
 26 int nc;
 27 
 28 // recursively calculate depths of nodes
 29 void getDepth(st *root, int dep)
 30 {
 31     if (root == NULL) {
 32         return;
 33     }
 34     depth[hash_key[root->key]] = dep;
 35     if (root->ll != NULL) {
 36         getDepth(root->ll, dep + 1);
 37     }
 38     if (root->rr != NULL) {
 39         getDepth(root->rr, dep + 1);
 40     }
 41 }
 42 
 43 // recursively construct a binary tree
 44 void constructBinaryTree(st *&root)
 45 {
 46     int tmp;
 47 
 48     scanf("%d", &tmp);
 49     if (tmp == 0) {
 50         root = NULL;
 51     } else {
 52         root = new st(tmp);
 53         ++nc;
 54         if (hash_key[tmp] == 0) {
 55             hash_key[tmp] = nc;
 56         }
 57         key_hash[nc] = tmp;
 58         constructBinaryTree(root->ll);
 59         constructBinaryTree(root->rr);
 60     }
 61 }
 62 
 63 // recursively initialize ancestor array
 64 void getParent(st *root)
 65 {
 66     if (root == NULL) {
 67         return;
 68     }
 69 
 70     // anc[x][0] is the direct parent of x.
 71     if (root->ll != NULL) {
 72         anc[hash_key[root->ll->key]][0] = hash_key[root->key];
 73         getParent(root->ll);
 74     }
 75     if (root->rr != NULL) {
 76         anc[hash_key[root->rr->key]][0] = hash_key[root->key];
 77         getParent(root->rr);
 78     }
 79 }
 80 
 81 // calculate LCA in O(log(n)) time
 82 int leastCommonAncestor(int x, int y)
 83 {
 84     int i;
 85 
 86     if (depth[x] < depth[y]) {
 87         return leastCommonAncestor(y, x);
 88     }
 89     for (i = 15; i >= 0; --i) {
 90         if (depth[anc[x][i]] >= depth[y]) {
 91             x = anc[x][i];
 92             if (depth[x] == depth[y]) {
 93                 break;
 94             }
 95         }
 96     }
 97     if (x == y) {
 98         return x;
 99     }
100 
101     for (i = 15; i >= 0; --i) {
102         if (anc[x][i] != anc[y][i]) {
103             // they'll finally be equal, think about the reason.
104             x = anc[x][i];
105             y = anc[y][i];
106         }
107     }
108 
109     // this is the direct parent of x
110     return anc[x][0];
111 }
112 
113 st *deleteTree(st *root)
114 {
115     if (NULL == root) {
116         return NULL;
117     }
118 
119     if (root->ll != NULL) {
120         root->ll = deleteTree(root->ll);
121     }
122     if (root->rr != NULL) {
123         root->rr = deleteTree(root->rr);
124     }
125     delete root;
126     root = NULL;
127 
128     return NULL;
129 }
130 
131 int main()
132 {
133     int ci, cc;
134     int i, j;
135     int x, y;
136     st *root;
137 
138     while (scanf("%d", &cc) == 1) {
139         for (ci = 0; ci < cc; ++ci) {
140             // data initialization 
141             memset(hash_key, 0, MAXN * sizeof(int));
142             memset(key_hash, 0, MAXN * sizeof(int));
143             memset(depth, 0, MAXN * sizeof(int));
144             memset(anc, 0, MAXN * 16 * sizeof(int));
145             nc = 0;
146             root = NULL;
147 
148             constructBinaryTree(root);
149             getParent(root);
150             getDepth(root, 1);
151             for (j = 1; j < 16; ++j) {
152                 for (i = 1; i <= nc; ++i) {
153                     anc[i][j] = anc[anc[i][j - 1]][j - 1];
154                 }
155             }
156             while (scanf("%d%d", &x, &y) == 2 && (x && y)) {
157                 if (hash_key[x] == 0 || hash_key[y] == 0) {
158                     printf("Not found in the tree.
");
159                 } else {
160                     printf("%d
", key_hash[leastCommonAncestor(hash_key[x], hash_key[y])]);
161                 }
162             }
163 
164             root = deleteTree(root);
165         }
166     }
167 
168     return 0;
169 }

解法3：Tarjan离线算法，并查集的妙用。

代码：

  1 // 4.7 Least Common Ancestor
  2 // Tarjan Offline Algorithm
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <unordered_map>
  6 #include <unordered_set>
  7 using namespace std;
  8 
  9 struct TreeNode {
 10     int val;
 11     TreeNode *left;
 12     TreeNode *right;
 13     
 14     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};
 15 };
 16 
 17 void constructTree(vector<TreeNode *> &nodes, 
 18                    unordered_set<TreeNode *> &checked)
 19 {
 20     int ll, rr;
 21     int i;
 22 
 23     for (i = 0; i < (int)nodes.size(); ++i) {
 24         checked.insert(nodes[i]);
 25     }
 26     for (i = 0; i < (int)nodes.size(); ++i) {
 27         scanf("%d%d", &ll, &rr);
 28         if (ll > 0) {
 29             nodes[i]->left = nodes[ll - 1];
 30             checked.erase(nodes[ll - 1]);
 31         }
 32         if (rr > 0) {
 33             nodes[i]->right = nodes[rr - 1];
 34             checked.erase(nodes[rr - 1]);
 35         }
 36     }
 37 }
 38 
 39 TreeNode *findRoot(TreeNode *node, unordered_map<TreeNode *, TreeNode *> &disjoint_set)
 40 {
 41     if (node != disjoint_set[node]) {
 42         disjoint_set[node] = findRoot(disjoint_set[node], disjoint_set);
 43     }
 44     
 45     return disjoint_set[node];
 46 }
 47 
 48 void tarjanLCA(TreeNode *root, unordered_map<TreeNode *, TreeNode *> &disjoint_set, 
 49                unordered_map<TreeNode *, unordered_map<TreeNode *, TreeNode *> > &query, 
 50                unordered_set<TreeNode *> &checked)
 51 {
 52     if (root == nullptr) {
 53         return;
 54     }
 55     
 56     disjoint_set[root] = root;
 57     if (root->left != nullptr) {
 58         tarjanLCA(root->left, disjoint_set, query, checked);
 59         disjoint_set[root->left] = root;
 60     }
 61     if (root->right != nullptr) {
 62         tarjanLCA(root->right, disjoint_set, query, checked);
 63         disjoint_set[root->right] = root;
 64     }
 65     checked.insert(root);
 66     
 67     if (query.find(root) == query.end()) {
 68         return;
 69     }
 70     
 71     unordered_map<TreeNode *, TreeNode *>::iterator it;
 72     for (it = query[root].begin(); it != query[root].end(); ++it) {
 73         if (it->second != nullptr) {
 74             // already solved, skip it
 75             continue;
 76         }
 77         if (checked.find(it->first) != checked.end()) {
 78             query[root][it->first] = query[it->first][root] = findRoot(it->first, disjoint_set);
 79         }
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int n;
 86     int i;
 87     int val;
 88     vector<TreeNode *> nodes;
 89     TreeNode *root;
 90     unordered_map<TreeNode *, TreeNode *> disjoint_set;
 91     unordered_map<TreeNode *, unordered_map<TreeNode *, TreeNode *> > query;
 92     unordered_map<TreeNode *, unordered_map<TreeNode *, TreeNode *> >::iterator it1;
 93     unordered_set<TreeNode *> checked;
 94     unordered_map<TreeNode *, TreeNode *>::iterator it2;
 95     int idx1, idx2;
 96     
 97     while (scanf("%d", &n) == 1 && n > 0) {
 98         nodes.resize(n);
 99         for (i = 0; i < n; ++i) {
100             scanf("%d", &val);
101             nodes[i] = new TreeNode(val);
102         }
103         constructTree(nodes, checked);
104         root = *(checked.begin());
105         checked.clear();
106         
107         while (scanf("%d%d", &idx1, &idx2) == 2 && (idx1 >= 0 && idx2 >= 0)) {
108             if (idx1 > idx2) {
109                 i = idx1;
110                 idx1 = idx2;
111                 idx2 = i;
112             }
113             query[nodes[idx1]][nodes[idx2]] = nullptr;
114             query[nodes[idx2]][nodes[idx1]] = nullptr;
115         }
116         // Tarjan Offline Algorithm
117         tarjanLCA(root, disjoint_set, query, checked);
118         
119         // print the results
120         for (it1 = query.begin(); it1 != query.end(); ++it1) {
121             for (it2 = (it1->second).begin(); it2 != (it1->second).end(); ++it2) {
122                 if (it1->first->val > it2->first->val) {
123                     continue;
124                 }
125                 printf("The least common ancestor of %d and %d is %d.
", 
126                        it1->first->val, it2->first->val, it2->second->val);
127             }
128         }
129         
130         // clear up
131         disjoint_set.clear();
132         checked.clear();
133         for (it1 = query.begin(); it1 != query.end(); ++it1) {
134             (it1->second).clear();
135         }
136         query.clear();
137     }
138     
139     return 0;
140 }