r*****b
发帖数: 8 | 1 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
第一轮:
经典stack题 pop, push, getmin
实现一下strcmp
第二轮:
打印一棵二叉树最深的路径
实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
注意一下 needle可能比haystack长.. (俺忘了这个..)
ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :( |
i**9
发帖数: 351 | |
z*s
发帖数: 209 | 3 感谢分享！Bless 楼主！
要相信自己，我连面试机会都没有。 |
d******a
发帖数: 238 | 4 感谢分享，加油！
顺便问下楼主 打印一棵二叉树最深的路径怎么解决的？
我的想法是递归得到所有的路径，然后保存最长的，然后打印。 |
r*****b
发帖数: 8 | 5 DFS, 遇到叶子节点以后, check一下当前stack里面的节点数, 如果大于current max,
那么更新; 否则就继续DFS, 直到结束
基本和你的想法一样吧.
【在 d******a 的大作中提到】
: 感谢分享，加油！
: 顺便问下楼主 打印一棵二叉树最深的路径怎么解决的？
: 我的想法是递归得到所有的路径，然后保存最长的，然后打印。
|
d******a
发帖数: 238 | 6 感谢分享，加油！
顺便问下楼主 打印一棵二叉树最深的路径怎么解决的？
我的想法是递归得到所有的路径，然后保存最长的，然后打印。 |
g*********s
发帖数: 1782 | 7 空间复杂度有点高。
不如保存每个子树的深度，然后从根出发，选深度更大的前进。
【在 d******a 的大作中提到】
: 感谢分享，加油！
: 顺便问下楼主 打印一棵二叉树最深的路径怎么解决的？
: 我的想法是递归得到所有的路径，然后保存最长的，然后打印。
|
d******a
发帖数: 238 | |
g*********s
发帖数: 1782 | 9 这个strstr的实现里为什么要考虑needle长于haystack？我试了一下，可以自然处理啊。
【在 r*****b 的大作中提到】
: 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
: 第一轮:
: 经典stack题 pop, push, getmin
: 实现一下strcmp
: 第二轮:
: 打印一棵二叉树最深的路径
: 实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
: 注意一下 needle可能比haystack长.. (俺忘了这个..)
: ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :(
|
g*********s
发帖数: 1782 | 10 你是保留这个叶节点，然后假定有父指针，沿着父指针找上去？
,
【在 r*****b 的大作中提到】
: DFS, 遇到叶子节点以后, check一下当前stack里面的节点数, 如果大于current max,
: 那么更新; 否则就继续DFS, 直到结束
: 基本和你的想法一样吧.
|
|
|
h**********d
发帖数: 4313 | 11 祝福下楼主
btw, facebook也没给我面试机会.. |
g*********s
发帖数: 1782 | 12
这道题板上大牛有定论了吗？
【在 r*****b 的大作中提到】
: 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
: 第一轮:
: 经典stack题 pop, push, getmin
: 实现一下strcmp
: 第二轮:
: 打印一棵二叉树最深的路径
: 实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
: 注意一下 needle可能比haystack长.. (俺忘了这个..)
: ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :(
|
l*****a
发帖数: 14598 | 13 这题需要大牛吗？
只能遍历，找到所有路径，保留最大的
还能有啥别的招
【在 g*********s 的大作中提到】
:
: 这道题板上大牛有定论了吗？
|
g*********s
发帖数: 1782 | 14 我需要假定带父指针，两次遍历。
第一次计算出树高度，第二次根据树高找最深叶节点，然后根据父指针找上去。
找所有路径开销太大了。
【在 l*****a 的大作中提到】
: 这题需要大牛吗？
: 只能遍历，找到所有路径，保留最大的
: 还能有啥别的招
|
j*****u
发帖数: 1133 | 15 题目没有说就是没有父指针，而且计算树的高度也是要遍历所有节点的。
这个题没有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*********s
发帖数: 1782 | 16 怎么记录到当前节点的路径？
【在 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*********s
发帖数: 1782 | 17 又想了一下，这个题用一遍BFS就可以了。在遍历的同时记录p[n]和d[n]，这里p[n]是
节点n的父节
点，d[n]是root到节点n的距离。实际是Dijkstra的特例。
由于是树结构，时间复杂度O(N)，空间复杂度O(N)。
【在 g*********s 的大作中提到】
: 怎么记录到当前节点的路径？
|
j*****u
发帖数: 1133 | 18 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*****u
发帖数: 1133 | 19 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*********s
发帖数: 1782 | 20 你这个怎么能保证时间复杂度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*****u
发帖数: 1133 | 21 你是对的，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*********s
发帖数: 1782 | 22 我感觉即使是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**9
发帖数: 351 | 23 写了一个
”打印一棵二叉树最深的路径“
大家讨论讨论，这个程序打印所有的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*********s
发帖数: 1782 | 24 你这个还是两次遍历。
【在 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***n
发帖数: 166 | 25 能用DP吗?
扫描一遍，把所有node的深度都保存在一个数组里，然后从root开始，找深度最大的一
个child，扫描需要时间O（N），寻找需要时间O（n log n)
总共时间O（N），空间O(N)
【在 r*****b 的大作中提到】
: 刚面试完第二轮.. 估计要挂.. 题很简单.. 今儿中邪了.
: 第一轮:
: 经典stack题 pop, push, getmin
: 实现一下strcmp
: 第二轮:
: 打印一棵二叉树最深的路径
: 实现一下strstr(char* haystack, char* needle) 不可以用strlen等库函数
: 注意一下 needle可能比haystack长.. (俺忘了这个..)
: ps. 小印不善啊... 放我一个小时的鸽子... 唉.. :(
|
g*********s
发帖数: 1782 | 26 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***n
发帖数: 166 | 27 抱歉，我说错了
我的方法复杂度太大了
【在 g*********s 的大作中提到】
: i don't see why this is dp. u mean dfs?
|
n*****e
发帖数: 2 | 28 打印一棵二叉树最深的路径 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**********r
发帖数: 27 | |
g**********r
发帖数: 27 | 30 A very good link about the strstr problem
http://vijayinterviewquestions.blogspot.com/2007/07/write-c-cod
to-implement-strstr-search.html |
|
|
g***s
发帖数: 3811 | 31 "寻找需要时间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 的大作中提到】
: 能用DP吗?
: 扫描一遍，把所有node的深度都保存在一个数组里，然后从root开始，找深度最大的一
: 个child，扫描需要时间O（N），寻找需要时间O（n log n)
: 总共时间O（N），空间O(N)
|
f*********i
发帖数: 197 | 32 对树的最长路径,只要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***y
发帖数: 2546 | 33 简单说一下大概的意思？
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;
|
