不要拿法律当挡箭牌（图）zz - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

不要拿法律当挡箭牌（图）zz

不要拿法律当挡箭牌（图）zz# Joke - 肚皮舞运动

L*n2011-03-07 08:03

1 楼

Binary Tree:
A -> B -> C -> D
-> E -> F
-> G -> H
-> I -> J
finding the longest path

v*y2011-03-07 08:03

2 楼

p*w2011-03-07 08:03

3 楼

不要拿法律当挡箭牌（图）zz
如果看不见图，最大可能是你自己被铲子盾了，就不要看了。

j*w2011-03-07 08:03

4 楼

BFS, then the path from root to the last leave is the answer.

D*X2011-03-07 08:03

5 楼

嗯，留着夏天泡茶。

x*u2011-03-07 08:03

6 楼

J点？

【在 p*********w 的大作中提到】

: 不要拿法律当挡箭牌（图）zz
: 如果看不见图，最大可能是你自己被铲子盾了，就不要看了。

L*n2011-03-07 08:03

7 楼

牛人能再详细解释一下吗，多谢！

v*y2011-03-07 08:03

8 楼

菊花可以泡茶啊？

【在 D*X 的大作中提到】

: 嗯，留着夏天泡茶。

p*e2011-03-07 08:03

9 楼

不要拿法律当挡箭牌

【在 x****u 的大作中提到】

: J点？

m*e2011-03-07 08:03

10 楼

人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。

【在 L********n 的大作中提到】

: 牛人能再详细解释一下吗，多谢！

h*e2011-03-07 08:03

11 楼

漂亮

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

p*w2011-03-07 08:03

12 楼

你说得太好了。我借用你的说法吧。

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

: 不要拿法律当挡箭牌

L*n2011-03-07 08:03

13 楼

是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
google电面被受打击...
Anyway, now I have figured it out

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

: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。

f*c2011-03-07 08:03

14 楼

漂亮，好像闻到了菊花的香味

a*b2011-03-07 08:03

15 楼

反共反到搞藏独么，joke版也是有自己的底线的

m*e2011-03-07 08:03

16 楼

这些公司最好还是多准备准备再上，呵呵，碰运气基本上很难，就是浪费机会。

【在 L********n 的大作中提到】

: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out

T*m2011-03-07 08:03

17 楼

泡茶的是专门的菊花吧？如杭白菊和野菊花。
你的花是自己种的，还是今年才买的？很好看。

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

: 菊花可以泡茶啊？

z*n2011-03-07 08:03

18 楼

原来土共在搞藏独？怪不得需要进藏许可证呢。

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

: 反共反到搞藏独么，joke版也是有自己的底线的

f*42011-03-07 08:03

19 楼

找到工作后的第一件事情就是为找下一份工作做准备～

【在 L********n 的大作中提到】

: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out

L*a2011-03-07 08:03

20 楼

好看。怎么才开啊，我家的都谢了。

p*e2011-03-07 08:03

21 楼

期待赵云好诗

B*82011-03-07 08:03

22 楼

How to remember path in BFT?
How about using DFT (C#)?
List MaxPath(Node r) {
if (r==null) return new List();
List L = MaxPath(r.Left), R=MaxPath(r.Right);
if (L.length > R.length) { L.Add(r); return L; }
else { R.Add(r); return R; }
}

v*y2011-03-07 08:03

23 楼

自己种的呀，年年都开，从来没泡过茶，呵

【在 T*******m 的大作中提到】

: 泡茶的是专门的菊花吧？如杭白菊和野菊花。
: 你的花是自己种的，还是今年才买的？很好看。

s*n2011-03-07 08:03

24 楼

depends on how longest path is defined.
assume that he asked a path in undirected graph.
the best solution for binary three is always recusrive solution since it is
elegant and simple for the interview purpose.
Hight (i) = 1 + max(Height(i.leftNode), Height(i.rightNode))
Height (null node) =0;
LongthestPath(i) = 1+ Height(i.left) + Height(i.right).

【在 L********n 的大作中提到】

: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out

v*y2011-03-07 08:03

25 楼

秋高气爽吧，就都开了，全是我妈在照顾

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

: 好看。怎么才开啊，我家的都谢了。

s*n2011-03-07 08:03

26 楼

the answer is wrong.

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

: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。

b*r2011-03-07 08:03

27 楼

find depth of each node and the node with largest sum of left depth and
right depth is the one

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

: the answer is wrong.

d*d2011-03-07 08:03

28 楼

题目说明白点。

【在 L********n 的大作中提到】

: Binary Tree:
: A -> B -> C -> D
: -> E -> F
: -> G -> H
: -> I -> J
: finding the longest path

a*o2011-03-07 08:03

29 楼

不会是问最深的结点这么简单，应该是说把边都看作无向的，然后找一条最长路径

【在 j**w 的大作中提到】

: BFS, then the path from root to the last leave is the answer.

d*l2011-03-07 08:03

30 楼

对于每个节点，用其左右两边的最长路径之和去更新最大值应该就可以

a*o2011-03-07 08:03

31 楼

完整的应该是对于每个节点i，以它为根的子树的最长路径为m(i)=max(m(i->left), m(
i->right), n(i->left) + n(i->right) + 1), n(i)表示以i为根的树的最大深度

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

: 对于每个节点，用其左右两边的最长路径之和去更新最大值应该就可以

r*l2011-03-07 08:03

32 楼

用一个queue进行BFS，queue里面节点记录level以便找最大，记录parent以便回溯打印
最长路径

j*l2011-03-07 08:03

33 楼

struct Node
{
Node* left;
Node* right;
};
int longest_path = 0;
int GetTreeHeight(Node* root)
{
if (root == NULL)
return 0;
int left_height = GetTreeHeight(root->left);
int right_height = GetTreeHeight(root->right);
longest_path = max(longest_path, left_height + right_height);

return max(left_height, right_height) + 1;
}

i*e2011-03-07 08:03

34 楼

Please note that it's not enough to return only the maximum depth. The
question clearly specifies to return the longest path.
Using DFS is the correct answer. BFS can work too, but requires either:
1) Parent pointer in each node to get the longest path from leaf up to the
root.
2) An extra data structure to record the path from root to leaf, which is
also pushed into the queue.
DFS has a simple solution:
void getLongestPathDFS(Node *root, vector &path,
vector &longestPath) {
if (!root)
return;
path.push_back(root);
if (path.size() > longestPath.size())
longestPath = path;
getLongestPathDFS(root->left, path, longestPath);
getLongestPathDFS(root->right, path, longestPath);
path.pop_back();
}
vector getLongestPathDFS(Node *root) {
vector longestPath;
getLongestPathDFS(root, vector(), longestPath);
return longestPath;
}
PS: It's not necessary to return a vector of nodes as the longest path. At each node, there's only two possible ways, left or right. Therefore, representing left as 0 and right as 1, you can use a bitmap data structure to record the maximum path from the root, which is more efficient in terms of speed and space.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

j*l2011-03-07 08:03

35 楼

要先向interviewer确认，是求二叉树的直径，也就是节点的最大距离。
最大距离的路径，一定穿过某棵子树(含整棵树的情形)的根节点A, 长度(边的条数)是A
的左子树的高度和右子树的高度之和。假定空树的高度为0，单节点树的高度为1。

j*l2011-03-07 08:03

36 楼

你这个求的是根节点到最深节点的路径(路径所含的节点个数可定义为树的高度), 不是树的直径(把树看成无向图，定义两个节点的距离为连通两个节点的路径的边数，求最大距离)

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

: Please note that it's not enough to return only the maximum depth. The
: question clearly specifies to return the longest path.
: Using DFS is the correct answer. BFS can work too, but requires either:
: 1) Parent pointer in each node to get the longest path from leaf up to the
: root.
: 2) An extra data structure to record the path from root to leaf, which is
: also pushed into the queue.
: DFS has a simple solution:
: void getLongestPathDFS(Node *root, vector &path,
: vector &longestPath) {