j********g
发帖数: 244 | 1 该怎么做？
好像在哪里看到这么个题，平时都是2nodes. | h****n
发帖数: 1093 | 2 有两个的了多个还不好做？先找两个的lca之后和第三个继续找lca 以此类推 当然效率
上有待提高
该怎么做？好像在哪里看到这么个题，平时都是2nodes.
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 j********g 的大作中提到】
: 该怎么做？
: 好像在哪里看到这么个题，平时都是2nodes.
| j********g
发帖数: 244 | 3
是啊 就是想知道有没有更高效的。。。。
【在 h****n 的大作中提到】
: 有两个的了多个还不好做？先找两个的lca之后和第三个继续找lca 以此类推 当然效率
: 上有待提高
:
: 该怎么做？好像在哪里看到这么个题，平时都是2nodes.
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
| d****n
发帖数: 1637 | 4 suppose binary tree root node is "root"
and all nodes pointers are in the array of
nodes[N];
// copied from leetcode.com
Node *lca2(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = lca2(root->left, p, q);
Node *R = lca2(root->right, p, q);
if (L && R) return root;
return L ? L : R;
}
Node *lca_aux(root, left, right )
{
if (left==right)
return lca2(left,right);
return lca2(root,lca2(root,left,right), lca_aux(left+1,right-1));
}
Node *lca(Node * root, nodes[], N){
return lca_aux(root, nodes[0], nodes[N-1])
} | C***U
发帖数: 2406 | 5 两个一组 找到lca 得到一串
找到后 找这些nodes的lca
依次继续
最后只剩一个node为止
【在 d****n 的大作中提到】
: suppose binary tree root node is "root"
: and all nodes pointers are in the array of
: nodes[N];
: // copied from leetcode.com
: Node *lca2(Node *root, Node *p, Node *q) {
: if (!root) return NULL;
: if (root == p || root == q) return root;
: Node *L = lca2(root->left, p, q);
: Node *R = lca2(root->right, p, q);
: if (L && R) return root;
| h****n
发帖数: 1093 | 6 刚想说 其实就是 divide and conquer
两个一组
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 C***U 的大作中提到】
: 两个一组 找到lca 得到一串
: 找到后 找这些nodes的lca
: 依次继续
: 最后只剩一个node为止
| d*********i
发帖数: 104 | 7 那假设找K个node的LCA,整个树node数为N,
求LCA的complexity是O(N),总的complexity是不是 N(K-1)?
【在 C***U 的大作中提到】
: 两个一组 找到lca 得到一串
: 找到后 找这些nodes的lca
: 依次继续
: 最后只剩一个node为止
| h****n
发帖数: 2094 | 8 俩俩的算？
【在 j********g 的大作中提到】
: 该怎么做？
: 好像在哪里看到这么个题，平时都是2nodes.
| t*********n
发帖数: 89 | 9 能不能递归返回每一个子树的所包含的给定节点，当一个节点其左右子树所含给定节点
之和为给定节点的总数的时候，那么这个节点就是公共子节点... |
|
