不要拿法律当挡箭牌（图）zz# Joke - 肚皮舞运动
L*n
1 楼
Binary Tree:
A -> B -> C -> D
-> E -> F
-> G -> H
-> I -> J
finding the longest path
A -> B -> C -> D
-> E -> F
-> G -> H
-> I -> J
finding the longest path
v*y
2 楼
p*w
3 楼
不要拿法律当挡箭牌（图）zz
如果看不见图，最大可能是你自己被铲子盾了，就不要看了。
如果看不见图，最大可能是你自己被铲子盾了，就不要看了。
j*w
4 楼
BFS, then the path from root to the last leave is the answer.
D*X
5 楼
嗯，留着夏天泡茶。
x*u
6 楼
J点？
【在 p*********w 的大作中提到】
: 不要拿法律当挡箭牌（图）zz
: 如果看不见图，最大可能是你自己被铲子盾了，就不要看了。
【在 p*********w 的大作中提到】
: 不要拿法律当挡箭牌（图）zz
: 如果看不见图，最大可能是你自己被铲子盾了，就不要看了。
L*n
7 楼
牛人能再详细解释一下吗，多谢！
v*y
8 楼
菊花可以泡茶啊？
【在 D*X 的大作中提到】
: 嗯，留着夏天泡茶。
【在 D*X 的大作中提到】
: 嗯，留着夏天泡茶。
p*e
9 楼
不要拿法律当挡箭牌
【在 x****u 的大作中提到】
: J点？
【在 x****u 的大作中提到】
: J点？
m*e
10 楼
人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。
【在 L********n 的大作中提到】
: 牛人能再详细解释一下吗，多谢！
【在 L********n 的大作中提到】
: 牛人能再详细解释一下吗，多谢！
h*e
11 楼
漂亮
【在 v******y 的大作中提到】
【在 v******y 的大作中提到】
p*w
12 楼
你说得太好了。我借用你的说法吧。
【在 p*****e 的大作中提到】
: 不要拿法律当挡箭牌
【在 p*****e 的大作中提到】
: 不要拿法律当挡箭牌
L*n
13 楼
是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
google电面被受打击...
Anyway, now I have figured it out
【在 m******e 的大作中提到】
: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。
google电面被受打击...
Anyway, now I have figured it out
【在 m******e 的大作中提到】
: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。
f*c
14 楼
漂亮，好像闻到了菊花的香味
a*b
15 楼
反共反到搞藏独么，joke版也是有自己的底线的
m*e
16 楼
这些公司最好还是多准备准备再上，呵呵，碰运气基本上很难，就是浪费机会。
【在 L********n 的大作中提到】
: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out
【在 L********n 的大作中提到】
: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out
T*m
17 楼
泡茶的是专门的菊花吧？如杭白菊和野菊花。
你的花是自己种的，还是今年才买的？很好看。
【在 v******y 的大作中提到】
: 菊花可以泡茶啊？
你的花是自己种的，还是今年才买的？很好看。
【在 v******y 的大作中提到】
: 菊花可以泡茶啊？
z*n
18 楼
原来土共在搞藏独？怪不得需要进藏许可证呢。
【在 a****b 的大作中提到】
: 反共反到搞藏独么，joke版也是有自己的底线的
【在 a****b 的大作中提到】
: 反共反到搞藏独么，joke版也是有自己的底线的
f*4
19 楼
找到工作后的第一件事情就是为找下一份工作做准备～
【在 L********n 的大作中提到】
: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out
【在 L********n 的大作中提到】
: 是准备不充分。因为突然的原因必须马上找工作，工作中做算法很少
: google电面被受打击...
: Anyway, now I have figured it out
L*a
20 楼
好看。怎么才开啊，我家的都谢了。
p*e
21 楼
期待赵云好诗
B*8
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; }
}
How about using DFT (C#)?
List
if (r==null) return new List
List
if (L.length > R.length) { L.Add(r); return L; }
else { R.Add(r); return R; }
}
v*y
23 楼
自己种的呀，年年都开，从来没泡过茶，呵
【在 T*******m 的大作中提到】
: 泡茶的是专门的菊花吧？如杭白菊和野菊花。
: 你的花是自己种的，还是今年才买的？很好看。
【在 T*******m 的大作中提到】
: 泡茶的是专门的菊花吧？如杭白菊和野菊花。
: 你的花是自己种的，还是今年才买的？很好看。
s*n
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
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*y
25 楼
秋高气爽吧，就都开了，全是我妈在照顾
【在 L******a 的大作中提到】
: 好看。怎么才开啊，我家的都谢了。
【在 L******a 的大作中提到】
: 好看。怎么才开啊，我家的都谢了。
s*n
26 楼
the answer is wrong.
【在 m******e 的大作中提到】
: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。
【在 m******e 的大作中提到】
: 人家已经说得够清楚了，如果这你还不明白，只能说你面试准备的还太不充分。
b*r
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.
right depth is the one
【在 s*****n 的大作中提到】
: the answer is wrong.
d*d
28 楼
题目说明白点。
【在 L********n 的大作中提到】
: Binary Tree:
: A -> B -> C -> D
: -> E -> F
: -> G -> H
: -> I -> J
: finding the longest path
【在 L********n 的大作中提到】
: Binary Tree:
: A -> B -> C -> D
: -> E -> F
: -> G -> H
: -> I -> J
: finding the longest path
a*o
29 楼
不会是问最深的结点这么简单，应该是说把边都看作无向的，然后找一条最长路径
【在 j**w 的大作中提到】
: BFS, then the path from root to the last leave is the answer.
【在 j**w 的大作中提到】
: BFS, then the path from root to the last leave is the answer.
d*l
30 楼
对于每个节点，用其左右两边的最长路径之和去更新最大值应该就可以
a*o
31 楼
完整的应该是对于每个节点i，以它为根的子树的最长路径为m(i)=max(m(i->left), m(
i->right), n(i->left) + n(i->right) + 1), n(i)表示以i为根的树的最大深度
【在 d*******l 的大作中提到】
: 对于每个节点，用其左右两边的最长路径之和去更新最大值应该就可以
i->right), n(i->left) + n(i->right) + 1), n(i)表示以i为根的树的最大深度
【在 d*******l 的大作中提到】
: 对于每个节点，用其左右两边的最长路径之和去更新最大值应该就可以
r*l
32 楼
用一个queue进行BFS，queue里面节点记录level以便找最大，记录parent以便回溯打印
最长路径
最长路径
j*l
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;
}
{
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*e
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
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
vector
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
vector
getLongestPathDFS(root, vector
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*l
35 楼
要先向interviewer确认，是求二叉树的直径，也就是节点的最大距离。
最大距离的路径，一定穿过某棵子树(含整棵树的情形)的根节点A, 长度(边的条数)是A
的左子树的高度和右子树的高度之和。假定空树的高度为0，单节点树的高度为1。
最大距离的路径，一定穿过某棵子树(含整棵树的情形)的根节点A, 长度(边的条数)是A
的左子树的高度和右子树的高度之和。假定空树的高度为0，单节点树的高度为1。
j*l
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) {
【在 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
: vector
相关阅读
看金星如何评论乞讨者！交部发言人很有幽默感 (转载)Re: 李咏得的是喉癌，治疗去的是美国的梅奥诊所 (转载)开了快俩月的 model 3，很不错呀LOL 偶然发现两年前唱的《捉小留》简直是我的经典之作 (转载)万圣节送大家一首enter sandman LoL听说：女人打男人被称为“勇敢”！魔鬼池之谜!历史上最幸运的男人!59魔改，依旧五对负重轮 (转载)呆湾的民主很喜感阿一尊还是很在意Trump的 (转载)京东最新的广告文案“不涂口红的你，和男人有什么区别”今天看了hunt killer一个人的内心可以阴暗到什么程度我的狗死了金庸死了墨西哥最大毒枭之一毕业于华东政法大学 (转载)男人眼里，外面没吃过的“屎”都是新鲜的！贱货川普要在11月前，给中产阶级减税！！！ (转载)