w**t
发帖数: 23 | 1 小弟在看careercup，其中有一题是求二叉树两个节点的Lowest Common Ancestor。
书中先给出一种解法：
1 public Tree commonAncestor(Tree root, Tree p, Tree q) {
2 if (covers(root.left, p) && covers(root.left, q))
3 return commonAncestor(root.left, p, q);
4 if (covers(root.right, p) && covers(root.right, q))
5 return commonAncestor(root.right, p, q);
6 return root;
7 }
8 private boolean covers(Tree root, Tree p) { /* is p a child of root?
*/
9 if (root == null) return false;
10 if (root == p) return true;
11 return covers(root.left, p) || covers(root.right, p);
12 }
此解法很简单，请问复杂度是O（n）对吗？因为O(n) = 2n + O(n/2).（理想状态，二
叉树平
衡）
因为此解法要多次访问一些节点，后来又给了一个解法，是统计当前节点包含p，q中几
个的，小弟的
考虑是：这种解法依然要多次访问一些节点啊，且时间复杂度也是O(n)啊，对吗？
多谢指教
第二种解法代码如下：
1 static int TWO_NODES_FOUND = 2;
2 static int ONE_NODE_FOUND = 1;
3 static int NO_NODES_FOUND = 0;
4
5 // Checks how many “special” nodes are located under this root
6 int covers(TreeNode root, TreeNode p, TreeNode q) {
7 int ret = NO_NODES_FOUND;
8 if (root == null) return ret;
9 if (root == p || root == q) ret += 1;
10 ret += covers(root.left, p, q);
11 if(ret == TWO_NODES_FOUND) // Found p and q
12 return ret;
13 return ret + covers(root.right, p, q);
14 }
15
16 TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
17 if (q == p && (root.left == q || root.right == q)) return root;
18 int nodesFromLeft = covers(root.left, p, q); // Check left side
19 if (nodesFromLeft == TWO_NODES_FOUND) {
20 if(root.left == p || root.left == q) return root.left;
21 else return commonAncestor(root.left, p, q);
22 } else if (nodesFromLeft == ONE_NODE_FOUND) {
23 if (root == p) return p;
24 else if (root == q) return q;
25 }
26 int nodesFromRight = covers(root.right, p, q); // Check right side
27 if(nodesFromRight == TWO_NODES_FOUND) {
28 if(root.right == p || root.right == q) return root.right;
29 else return commonAncestor(root.right, p, q);
30 } else if (nodesFromRight == ONE_NODE_FOUND) {
31 if (root == p) return p;
32 else if (root == q) return q;
33 }
34 if (nodesFromLeft == ONE_NODE_FOUND &&
35 nodesFromRight == ONE_NODE_FOUND) return root;
36 else return null;
37 } | j*****u
发帖数: 1133 | 2 粗看了一下，上面的解法应该不是O(n)的
O(n)解法可以这样，DFS的时候得到p和q的从root到它们的path，这个是O(n)的
然后把其中一个path放进hash set里，另外一个path找到第一个set里存在的node就是
lowest common ancestor，这一步是O(log n)
所以是O(n)的 | v*******7
发帖数: 187 | 3 我记得通用的解法没有那么复杂，就是recursion就能做了：
node* LCA(node *root, node *p, node *q) {
if (!root) return NULL; // tree is empty, base case
if (root == p || root == q) return root; // base case
node *l = LCA(root->left, p, q);
node *q = LCA(root->right, p, q);
if (l&&q) { return root; }
else if(l) { return l; }
else { return r; }
}
And the time complexity is O(N) since for the worst case each node has been
visited once by DFS. The space complexity is O(1).
【在 j*****u 的大作中提到】
: 粗看了一下，上面的解法应该不是O(n)的
: O(n)解法可以这样，DFS的时候得到p和q的从root到它们的path，这个是O(n)的
: 然后把其中一个path放进hash set里，另外一个path找到第一个set里存在的node就是
: lowest common ancestor，这一步是O(log n)
: 所以是O(n)的
| g*********s
发帖数: 1782 | 4 node *r, not q.
【在 v*******7 的大作中提到】
: 我记得通用的解法没有那么复杂，就是recursion就能做了：
: node* LCA(node *root, node *p, node *q) {
: if (!root) return NULL; // tree is empty, base case
: if (root == p || root == q) return root; // base case
: node *l = LCA(root->left, p, q);
: node *q = LCA(root->right, p, q);
: if (l&&q) { return root; }
: else if(l) { return l; }
: else { return r; }
: }
| v*******7
发帖数: 187 | 5
什么意思？没明白。
【在 g*********s 的大作中提到】
: node *r, not q.
| j*****u
发帖数: 1133 | 6 nice solution, but it does not check whether p and q both exists. e.g. if q
doesn't exist the function returns p.
【在 v*******7 的大作中提到】
: 我记得通用的解法没有那么复杂，就是recursion就能做了：
: node* LCA(node *root, node *p, node *q) {
: if (!root) return NULL; // tree is empty, base case
: if (root == p || root == q) return root; // base case
: node *l = LCA(root->left, p, q);
: node *q = LCA(root->right, p, q);
: if (l&&q) { return root; }
: else if(l) { return l; }
: else { return r; }
: }
| i**9
发帖数: 351 | 7 既然这个通用算法能够O(n)解决 LCA,怎么大部分地方喜欢讨论用Range Minimum Query
(RMQ) 来解决 LCA
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowest
【在 v*******7 的大作中提到】
: 我记得通用的解法没有那么复杂，就是recursion就能做了：
: node* LCA(node *root, node *p, node *q) {
: if (!root) return NULL; // tree is empty, base case
: if (root == p || root == q) return root; // base case
: node *l = LCA(root->left, p, q);
: node *q = LCA(root->right, p, q);
: if (l&&q) { return root; }
: else if(l) { return l; }
: else { return r; }
: }
| v*******7
发帖数: 187 | 8
q
Yes，this is one problem for this solution that I should claim.
【在 j*****u 的大作中提到】
: nice solution, but it does not check whether p and q both exists. e.g. if q
: doesn't exist the function returns p.
| d******u
发帖数: 397 | 9 如果p和q不同时在树中存在的话，那他们的LCA应该是什么呢？是null还是root
在vilan0607的解法之前，search一下p和q是否存在不就能解决这个问题了，如果有一
个不存在，就不用往下做了，返回null或者root
不知说的对不对 | v*******7
发帖数: 187 | 10 Sure, I know the solutions of cover().
For my solution, you can first perform an covercheck checking whether p and
q exist
in the tree. And actually, this check is not difficult, just DFS is enough
which cost
O(N) in time complexity. if both p and q exist in the, you can call the
recursion
solution that I posted. totally, the time complexity is still O(N), space
complexity
is O(1).
Another solution that I have is time complexity O(lgN) while space
complexity is O(N)
which should consider the height of p and q in the tree and also involves
hashing as
well as parent pointers.
【在 d******u 的大作中提到】
: 如果p和q不同时在树中存在的话，那他们的LCA应该是什么呢？是null还是root
: 在vilan0607的解法之前，search一下p和q是否存在不就能解决这个问题了，如果有一
: 个不存在，就不用往下做了，返回null或者root
: 不知说的对不对
| | | i**9
发帖数: 351 | 11 这个算法好像有点问题
if (root == p || root == q) return root; // base case
这一步应该是
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
那个 range minimum query算法比这个麻烦，但是介绍的反而多
【在 v*******7 的大作中提到】
: 我记得通用的解法没有那么复杂，就是recursion就能做了：
: node* LCA(node *root, node *p, node *q) {
: if (!root) return NULL; // tree is empty, base case
: if (root == p || root == q) return root; // base case
: node *l = LCA(root->left, p, q);
: node *q = LCA(root->right, p, q);
: if (l&&q) { return root; }
: else if(l) { return l; }
: else { return r; }
: }
| v*******7
发帖数: 187 | 12
我想过这个问题，可是也有个问题，比如
root
/ \
p n1
/ \
q n2
如果用if(root->left==p || root->left==q || root->right ==p || root->right ==
q)， root
就成为了LCA of p and q, 但是，我觉得不应该是p吗？
【在 i**9 的大作中提到】
: 这个算法好像有点问题
: if (root == p || root == q) return root; // base case
: 这一步应该是
: if(root->left==p || root->left==q || root->right ==p || root->right ==q)
: {
: return root;
: }
: 那个 range minimum query算法比这个麻烦，但是介绍的反而多
| l*****a
发帖数: 559 | 13 问一句有没有parent pointer撒。
wiki上写的是O（h)。
In a tree data structure where each node points to its parent, the lowest
common ancestor can be easily determined by finding the first intersection
of the paths from v and w to the root. In general, the computational time
required for this algorithm is O(h) where h is the height of the tree (
length of longest path from a leaf to the root). However, there exist
several algorithms for processing trees so that lowest common ancestors may
be found more quickly, in constant time per query after a linear time
preprocessing stage. | j*******r
发帖数: 20 | 14 RMQ可以做到O(n)时间预处理，然后O(1)时间回答一个query。。。
Query
【在 i**9 的大作中提到】
: 既然这个通用算法能够O(n)解决 LCA,怎么大部分地方喜欢讨论用Range Minimum Query
: (RMQ) 来解决 LCA
: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowest
| g*********s
发帖数: 1782 | 15 i don't think this is right given the code. it's also confusing.
【在 v*******7 的大作中提到】
: 我记得通用的解法没有那么复杂，就是recursion就能做了：
: node* LCA(node *root, node *p, node *q) {
: if (!root) return NULL; // tree is empty, base case
: if (root == p || root == q) return root; // base case
: node *l = LCA(root->left, p, q);
: node *q = LCA(root->right, p, q);
: if (l&&q) { return root; }
: else if(l) { return l; }
: else { return r; }
: }
| g*********s
发帖数: 1782 | 16 yes, i suspect the above recursion could be exponential, as there are a
lot of duplicate computation.
【在 j*****u 的大作中提到】
: 粗看了一下，上面的解法应该不是O(n)的
: O(n)解法可以这样，DFS的时候得到p和q的从root到它们的path，这个是O(n)的
: 然后把其中一个path放进hash set里，另外一个path找到第一个set里存在的node就是
: lowest common ancestor，这一步是O(log n)
: 所以是O(n)的
| C***y
发帖数: 2546 | 17 If it's assumed that a node is also the ancestor of itself(according to the
definition), then it's correct. However, the situations that only one or no
provided node exists in the tree need further consideration.
【在 g*********s 的大作中提到】
: i don't think this is right given the code. it's also confusing.
|
|
