极速前进开播了，请的人真奇怪 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>TVChinese - 中文电视

极速前进开播了，请的人真奇怪

极速前进开播了，请的人真奇怪# TVChinese - 中文电视

r*b2016-07-08 07:07

1 楼

刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
第一轮:
经典stack题 pop, push, getmin
实现一下strcmp
第二轮:
打印一棵二叉树最深的路径
实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
注意一下 needle可能比haystack长.. (俺忘了这个..)
ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :(

N*e2016-07-08 07:07

2 楼

郭晶晶，刘翔这么大牌都请到了，
金星名气也还行，
其它都是什么鬼

i*92016-07-08 07:07

3 楼

thanks for sharing

z*s2016-07-08 07:07

4 楼

感谢分享！Bless 楼主！
要相信自己，我连面试机会都没有。

d*a2016-07-08 07:07

5 楼

感谢分享，加油！
顺便问下楼主打印一棵二叉树最深的路径怎么解决的？
我的想法是递归得到所有的路径，然后保存最长的，然后打印。

r*b2016-07-08 07:07

6 楼

DFS, 遇到叶子节点以后, check一下当前stack里面的节点数, 如果大于current max,
那么更新; 否则就继续DFS, 直到结束
基本和你的想法一样吧.

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

: 感谢分享，加油！
: 顺便问下楼主打印一棵二叉树最深的路径怎么解决的？
: 我的想法是递归得到所有的路径，然后保存最长的，然后打印。

d*a2016-07-08 07:07

7 楼

感谢分享，加油！
顺便问下楼主打印一棵二叉树最深的路径怎么解决的？
我的想法是递归得到所有的路径，然后保存最长的，然后打印。

g*s2016-07-08 07:07

8 楼

空间复杂度有点高。
不如保存每个子树的深度，然后从根出发，选深度更大的前进。

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

: 感谢分享，加油！
: 顺便问下楼主打印一棵二叉树最深的路径怎么解决的？
: 我的想法是递归得到所有的路径，然后保存最长的，然后打印。

d*a2016-07-08 07:07

9 楼

嗯，跟我想法一样。

g*s2016-07-08 07:07

10 楼

这个strstr的实现里为什么要考虑needle长于haystack？我试了一下，可以自然处理啊。

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

: 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
: 第一轮:
: 经典stack题 pop, push, getmin
: 实现一下strcmp
: 第二轮:
: 打印一棵二叉树最深的路径
: 实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
: 注意一下 needle可能比haystack长.. (俺忘了这个..)
: ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :(

g*s2016-07-08 07:07

11 楼

你是保留这个叶节点，然后假定有父指针，沿着父指针找上去？

,

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

: DFS, 遇到叶子节点以后, check一下当前stack里面的节点数, 如果大于current max,
: 那么更新; 否则就继续DFS, 直到结束
: 基本和你的想法一样吧.

h*d2016-07-08 07:07

12 楼

祝福下楼主
btw, facebook也没给我面试机会..

g*s2016-07-08 07:07

13 楼

这道题板上大牛有定论了吗？

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

l*a2016-07-08 07:07

14 楼

这题需要大牛吗？
只能遍历，找到所有路径，保留最大的
还能有啥别的招

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

:
: 这道题板上大牛有定论了吗？

g*s2016-07-08 07:07

15 楼

我需要假定带父指针，两次遍历。
第一次计算出树高度，第二次根据树高找最深叶节点，然后根据父指针找上去。
找所有路径开销太大了。

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

: 这题需要大牛吗？
: 只能遍历，找到所有路径，保留最大的
: 还能有啥别的招

j*u2016-07-08 07:07

16 楼

题目没有说就是没有父指针，而且计算树的高度也是要遍历所有节点的。
这个题没有tricky的解法，就是要么
DFS w/ backtracking，维护两个stack，一个记录root到当前节点的path，另一个记录
max，每次到了叶节点比较两个stack的节点数目并update max if necessary
要么BFS，queue node里面包含从root到该节点的path，返回queue最后一个node里的
path
时间都是O(n)，空间DFS好一些

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

: 我需要假定带父指针，两次遍历。
: 第一次计算出树高度，第二次根据树高找最深叶节点，然后根据父指针找上去。
: 找所有路径开销太大了。

g*s2016-07-08 07:07

17 楼

怎么记录到当前节点的路径？

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

: 题目没有说就是没有父指针，而且计算树的高度也是要遍历所有节点的。
: 这个题没有tricky的解法，就是要么
: DFS w/ backtracking，维护两个stack，一个记录root到当前节点的path，另一个记录
: max，每次到了叶节点比较两个stack的节点数目并update max if necessary
: 要么BFS，queue node里面包含从root到该节点的path，返回queue最后一个node里的
: path
: 时间都是O(n)，空间DFS好一些

g*s2016-07-08 07:07

18 楼

又想了一下，这个题用一遍BFS就可以了。在遍历的同时记录p[n]和d[n]，这里p[n]是
节点n的父节
点，d[n]是root到节点n的距离。实际是Dijkstra的特例。
由于是树结构，时间复杂度O(N)，空间复杂度O(N)。

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

: 怎么记录到当前节点的路径？

j*u2016-07-08 07:07

19 楼

DFS solution的full code，最后print出来的是正确的order因为经历了2次stack的
revert
void PrintDeepestPath(TreeNode root)
{
if (root != null)
{
var maxPath = new Stack();
DFS(root, new Stack(), maxPath);
while (maxPath.Count > 0)
Console.WriteLine(maxPath.Pop().Value);
}
}
void DFS(TreeNode node, Stack currentPath, Stack maxPath)
{
currentPath.Push(node);
if (node.Left == null && node.Right == null)
{
if (currentPath.Count > maxPath.Count)
{
maxPath.Clear();
foreach (var n in currentPath)
maxPath.Push(n);
}
}
else
{
if (node.Left != null)
DFS(node.Left, currentPath, maxPath);
if (node.Right != null)
DFS(node.Right, currentPath, maxPath);
}
currentPath.Pop();
}

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

: 怎么记录到当前节点的路径？

j*u2016-07-08 07:07

20 楼

BFS是可以的，如果tree是balanced的，DFS时间也是O(n)而且只遍历一遍，空间是O(log n)。

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

: 又想了一下，这个题用一遍BFS就可以了。在遍历的同时记录p[n]和d[n]，这里p[n]是
: 节点n的父节
: 点，d[n]是root到节点n的距离。实际是Dijkstra的特例。
: 由于是树结构，时间复杂度O(N)，空间复杂度O(N)。

g*s2016-07-08 07:07

21 楼

你这个怎么能保证时间复杂度O(N)呢？
考虑特殊的BT，左儿子都是叶节点，按你这个方法，max_path要反复清空，复制current_
path，而
current_path的长度是1,2,...,n，那复杂度是O(N^2)啊。

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

: DFS solution的full code，最后print出来的是正确的order因为经历了2次stack的
: revert
: void PrintDeepestPath(TreeNode root)
: {
: if (root != null)
: {
: var maxPath = new Stack();
: DFS(root, new Stack(), maxPath);
: while (maxPath.Count > 0)
: Console.WriteLine(maxPath.Pop().Value);

j*u2016-07-08 07:07

22 楼

你是对的，worst case是O(n^2)，所有的左节点都是叶节点，这时候BFS时间会好些
但是tree是balanced情况下还是DFS略好
这个很像quicksort在worst case下fallback to mergesort :)

current_

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

: 你这个怎么能保证时间复杂度O(N)呢？
: 考虑特殊的BT，左儿子都是叶节点，按你这个方法，max_path要反复清空，复制current_
: path，而
: current_path的长度是1,2,...,n，那复杂度是O(N^2)啊。

g*s2016-07-08 07:07

23 楼

我感觉即使是bst也不能保证O(N)，虽然一下构造不出反例。
但是反过来，你怎么证明bst下是O(N)？
关键做DFS，即使是balanced bst，你遇到的current_path路径可能仍然恰好是严格单
增的，这样
你要反复清空max_path再复制current_path。这里有个sigma。

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

: 你是对的，worst case是O(n^2)，所有的左节点都是叶节点，这时候BFS时间会好些
: 但是tree是balanced情况下还是DFS略好
: 这个很像quicksort在worst case下fallback to mergesort :)
:
: current_

i*92016-07-08 07:07

24 楼

写了一个
”打印一棵二叉树最深的路径“
大家讨论讨论，这个程序打印所有的longest path,
void longestpath(Node * root,vector &v,int depth){
if(root==NULL){
return;
}
v.push_back(root->data);
if(v.size()==depth){
print(v);
return;
}
vector v2(v);
vector v3(v);
longestpath(root->left,v2,depth);
longestpath(root->right,v3,depth);
}
int main(){
Node * r = buildBST();
int d = maxdepth(r);
vector v;
longestpath(r,v,d);
return 0;
}

g*s2016-07-08 07:07

25 楼

你这个还是两次遍历。

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

: 写了一个
: ”打印一棵二叉树最深的路径“
: 大家讨论讨论，这个程序打印所有的longest path,
: void longestpath(Node * root,vector &v,int depth){
: if(root==NULL){
: return;
: }
: v.push_back(root->data);
: if(v.size()==depth){
: print(v);

E*n2016-07-08 07:07

26 楼

能用DP吗?
扫描一遍，把所有node的深度都保存在一个数组里，然后从root开始，找深度最大的一
个child，扫描需要时间O（N），寻找需要时间O（n log n)
总共时间O（N），空间O(N)

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

g*s2016-07-08 07:07

27 楼

i don't see why this is dp. u mean dfs?

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

: 能用DP吗?
: 扫描一遍，把所有node的深度都保存在一个数组里，然后从root开始，找深度最大的一
: 个child，扫描需要时间O（N），寻找需要时间O（n log n)
: 总共时间O（N），空间O(N)

E*n2016-07-08 07:07

28 楼

抱歉，我说错了
我的方法复杂度太大了

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

: i don't see why this is dp. u mean dfs?

n*e2016-07-08 07:07

29 楼

打印一棵二叉树最深的路径 is very similar to findMaxDepthInBST
int findMaxDepthInBST(node* root)
{
if(!root)
return;
int left = findMaxDepthInBST(root->left);
int right = findMaxDepthInBST(root->right);
if(left>right)
return left+1;
else return right+1;
}
For deepest path from root to leaf:
Just change "left/right" from type "int" to type "vector" and compare
left.length() and right.length() then push(root) to the longer vector
finally return the longer vector

g*r2016-07-08 07:07

30 楼

A very good link, solve the strstr problem http://vijayinterviewquestions.blogspot.com/2007/07/write-c-code-to-implement-strstr-search.html

g*r2016-07-08 07:07

31 楼

A very good link about the strstr problem
http://vijayinterviewquestions.blogspot.com/2007/07/write-c-cod
to-implement-strstr-search.html

g*s2016-07-08 07:07

32 楼

"寻找需要时间O（n log n)"
should be 寻找需要时间worst case O（n).
the worst case it also needs scan twice. average time is n+lgn

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

f*i2016-07-08 07:07

33 楼

对树的最长路径,只要DP就可以了啊,就是O(n)复杂度
public static Stack tree_print_longest_depth(BinaryTree root){
if(root==null)
return null;
Stack left = tree_print_longest_depth(root.leftChild);
Stack right = tree_print_longest_depth(root.rightChild);
if(left==null&&right==null){
Stack stack = new Stack ();
stack.push(root);
return stack;
}else if(left==null){
right.push(root);
return right;
}else if(right==null){
left.push(root);
return left;
}else if(left.size()>=right.size()){
left.push(root);
return left;
}else{
right.push(root);
return right;
}
}

C*y2016-07-08 07:07

34 楼

简单说一下大概的意思？

rightChild);

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

: 对树的最长路径,只要DP就可以了啊,就是O(n)复杂度
: public static Stack tree_print_longest_depth(BinaryTree root){
: if(root==null)
: return null;
: Stack left = tree_print_longest_depth(root.leftChild);
: Stack right = tree_print_longest_depth(root.rightChild);
: if(left==null&&right==null){
: Stack stack = new Stack ();
: stack.push(root);
: return stack;