百度云太TNND扯淡了 - 未名空间MITBBS历史存档

e*s2016-03-21 07:03

1 楼

题目是find lowest common ancestor in a binary tree (不是BST)。请问
（1）是不是一个node不能是本身的ancestor？比如如果p是q的parent, 则lowest common
ancestor是p的parent (而不是p)?
（2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
root ==q的情况？
请大牛讲讲，能给个标准的code就更感谢了！
Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
if(root == NULL)
return NULL;
if (p == NULL || q == NULL)
return NULL;
if(root->leftChild == p || root->leftChild == q || root->rightChild == p||
root->rightChild == q)
return root;
Node * L = LowestCommonAncestor(root->leftChild, p, q);
Node * R = LowestCommonAncestor(root->rightChild, p, q);
if(L != NULL && R != NULL)
return root;
else if (L != NULL)
return L;
else
return R;
}

p*w2016-03-21 07:03

2 楼

文匪报梁立人：艾未未是個什麼東西zz
http://paper.wenweipo.com/2011/04/18/WA1104180005.htm
梁立人
某報評論替最近備受注意的行為藝術家艾未未取了個很耐人尋味的名字─「特立獨行
者」，說白了，其實就是行為怪誕，有異於常人的人，更簡單的說，就是一般人所說的
神經病。其實，這對艾未未來說仍是一種恭維，因為在更多的人眼中，艾未未這種人，
簡直就是不知所謂的狗屎垃圾。
藝術家，本來是相當高尚的職業，但很多人頂著藝術的名義，做盡了不齒於人類的事
，玷污了藝術之名，就以艾未未為例，赤身露械是藝術，集體淫亂也稱藝術，由他所創
作的所謂「一虎八奶圖」，就是艾未未與其他4名肥腫難分的女人全裸合照，有網民稱
：「你只要看過他(艾未未)的照片，包保你馬上嘔吐並三天吃不下飯！」更有網絡報道
指出：「一個愛脫光了露出陽具的猥瑣肥漢，其形態可以說醜得石破天驚、神憎鬼厭，
換個人會被警察當流氓抓號子裡，只因為是艾未未，這就成了藝術或政治。」內地和海
外的藝術圈則將艾未未的行為藝術稱為「淫亂行為」，是對藝術和公序良俗的褻瀆。
如果艾未未只是玩世不恭，傷風敗俗也還罷了，然而，他變本加厲，將他宣淫販賤的
變態行為變成攻擊侮辱自己祖國的政治行動，在艾未未的「行為藝術」作品「我幹北京
天安門」中，艾未未對著天安門豎起中指，他稱「幹」就是「操」，中指是用來表示男
人的生殖器；在他的《再幹北京天安門》中，大腹便便的艾未未站在天安門前，其醜陋
無比的大肚腩上方寫著英文FUCK一詞。FUCK是流行的英語髒話，與普通話的「肏」、閩
南語的「幹」、四川話的「日」以及粵語的「屌」意思類似。這個字普遍被認為含有極
為冒犯和侮辱對方的意思。艾未未還特意解釋說：「為什麼不用『操』而用FUCK，是因
為僅以此作品獻給看得懂的、熱愛中國的國際友人。」
眾所周知，天安門有超過五百年的歷史，歷經數朝，是極具歷史意義的民族圖騰，公
開侮辱天安門，是對一個民族的挑釁，是不可饒恕的罪行。記得曾有人因塗污天安門被
治罪，為什麼這可惡的胖子可以公然侮辱天安門，卻沒有人奈何得了他，難道頂著藝術
之名，打著維權之義，就可以視國家尊嚴為無物，在十三億人頭上撒野？
即使有人認為，艾未未的行為在言論自由的範疇中，但同樣有更多人認為，艾未未的
言行，意在挑戰中國現政權，點燃顏色革命的火種，破壞社會穩定，罪不可恕，如果不
將艾未未治罪，絕非重視言論自由，而是對國家尊嚴的蔑視，是對十三億人感情的傷害！
雖然目前有關部門透露，拘押艾未未的原因是經濟犯罪，但無可諱言，艾未未更嚴重
的罪行是借維權之名，行破壞社會穩定之實，這種人以為借著西方強國的保護，便可以
肆無忌憚的在中國傷風敗俗，橫行霸道，所以，惟有數罪俱罰，嚴懲艾未未，將這西方
反華勢力製造的狗屎徹底剷除，並回貼在他們臉上，才足以平民憤，以儆效尤，回復天
安門廣場的乾淨和平靜。

a*e2016-03-21 07:03

3 楼

忽然一夜之间账号下从1.4T涨到2.6T
然后要求扩容，玩不起就算了，瞎整么

s*y2016-03-21 07:03

4 楼

This code is for BST right?

common
|

【在 e******s 的大作中提到】

: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)

x*02016-03-21 07:03

5 楼

1.4T? 厉害

【在 a***e 的大作中提到】

: 忽然一夜之间账号下从1.4T涨到2.6T
: 然后要求扩容，玩不起就算了，瞎整么

d*e2016-03-21 07:03

6 楼

好像是缺了查root==p || root==q的情况

common
|

【在 e******s 的大作中提到】

: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)

N*d2016-03-21 07:03

7 楼

申请账号后不久免费升级到5T。现在下载基本在百度云。这种网站被关是迟早的事

P*l2016-03-21 07:03

8 楼

不是吧

【在 s*****y 的大作中提到】

: This code is for BST right?
:
: common
: |

s*y2016-03-21 07:03

9 楼

24.3 Design an algorithm and write code to find the first common ancestor of
two
nodes in a binary search tree. Avoid storing additional nodes in a data
structure.

【在 P**l 的大作中提到】

: 不是吧

b*82016-03-21 07:03

10 楼

问题1其实不是问题，就是个理解问题，树上差了一级而已。面试碰到这种不清楚的，
直接问他澄清就是了。
（1）是不是一个node不能是本身的ancestor？比如如果p是q的parent, 则lowest
common ancestor是p的parent (而不是p)?

P*l2016-03-21 07:03

11 楼

code里哪里用到比大小了？

of

【在 s*****y 的大作中提到】

: 24.3 Design an algorithm and write code to find the first common ancestor of
: two
: nodes in a binary search tree. Avoid storing additional nodes in a data
: structure.

e*s2016-03-21 07:03

12 楼

这个题不是BST，就是一般的binary tree.
当然有别的题是BST里找。

of

【在 s*****y 的大作中提到】

: 24.3 Design an algorithm and write code to find the first common ancestor of
: two
: nodes in a binary search tree. Avoid storing additional nodes in a data
: structure.

e*s2016-03-21 07:03

13 楼

改了一下code, 请大家看看有什么问题没？
assume: 如果p是q的 parent/ancestor，则他们的lowest common ancestor是p的
parent
// lowest common ancestor in a binary tree
Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
if(!root)
return NULL;
if (!p|| !q)
return NULL;
if(root==p || root==q)
return NULL;
if(root->leftChild == p || root->leftChild == q || root->rightChild == p||
root->rightChild == q)
return root;
Node * L = LowestCommonAncestor(root->leftChild, p, q);
Node * R = LowestCommonAncestor(root->rightChild, p, q);
if(L != NULL && R != NULL)
return root;
else if (L != NULL)
return L;
else
return R;
}

【在 d**e 的大作中提到】

: 好像是缺了查root==p || root==q的情况
:
: common
: |

i*e2016-03-21 07:03

14 楼

1) 一个 node 可以是 ancestor。例如，如果 p 是 q 的 parent，那 LCA 就是 p 本
身。
2）解这题之前要问清楚面试官是否存在 parent 指针。如果存在的话比较简单，不用
递归解决。至于不存在 parent 指针的话，可以利用递归来解，要考虑的情况比较多。

common
|

【在 e******s 的大作中提到】

: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)

i*e2016-03-21 07:03

15 楼

Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
// this assumes p and q both exists in the binary tree
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // one of p or q is on one side
}
By the way, there is an optimization we could make in the above code. That is, what if we already found p and q in the left side of one subtree? Then as we recursively traverse back to the root, we DO NOT need to find if p and q exists in the right subtree (which for sure doesn't exist).

d*l2016-03-21 07:03

16 楼

这个方法不错。以前还真没想过没有parent该怎么弄，这个看起来更简洁

【在 i**********e 的大作中提到】

: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: Node *LCA(Node *root, Node *p, Node *q) {
: if (!root) return NULL;
: if (root == p || root == q) return root;
: Node *L = LCA(root->left, p, q);
: Node *R = LCA(root->right, p, q);
: if (L && R) return root; // if p and q are on both sides
: return L ? L : R; // one of p or q is on one side
: }

s*x2016-03-21 07:03

17 楼

A
B. C
DE. F G
This code is not right. Think the tree above, for A D, lca is A, you will
return C.

【在 i**********e 的大作中提到】

: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: Node *LCA(Node *root, Node *p, Node *q) {
: if (!root) return NULL;
: if (root == p || root == q) return root;
: Node *L = LCA(root->left, p, q);
: Node *R = LCA(root->right, p, q);
: if (L && R) return root; // if p and q are on both sides
: return L ? L : R; // one of p or q is on one side
: }

s*x2016-03-21 07:03

18 楼

A
B. C
DE. F G
This code is not right. Think the tree above, for A D, lca is A, you will
return C.

【在 i**********e 的大作中提到】

: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: Node *LCA(Node *root, Node *p, Node *q) {
: if (!root) return NULL;
: if (root == p || root == q) return root;
: Node *L = LCA(root->left, p, q);
: Node *R = LCA(root->right, p, q);
: if (L && R) return root; // if p and q are on both sides
: return L ? L : R; // one of p or q is on one side
: }

i*e2016-03-21 07:03

19 楼

It returns A for me :)

e*s2016-03-21 07:03

20 楼

Thanks a lot.

【在 i**********e 的大作中提到】

: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: Node *LCA(Node *root, Node *p, Node *q) {
: if (!root) return NULL;
: if (root == p || root == q) return root;
: Node *L = LCA(root->left, p, q);
: Node *R = LCA(root->right, p, q);
: if (L && R) return root; // if p and q are on both sides
: return L ? L : R; // one of p or q is on one side
: }

p*u2016-03-21 07:03

21 楼

Can you give a optimized solution? The optimized code looks not clean to me
.