c*******y 发帖数: 98 | 1 面筋都是按行打印,今天让我按列打印。手忙脚乱了一阵。。用了个父节点做出来的。
电面只写了一道题是不是挂了。。
更新题目具体内容:
按列打印,
a
/ \
b c
/
d
/
e
/
f
结果:
f
b e
a d
c
我刚发现,我的方法错了,老印最后没提醒我。已挂无悬念。
现在想到的方法是直接DFS,把column和value放到map
value>里,然后直接用map里的信息打印就好了。空间大一点但简单易操作。
fuck me....
新写了个,大伙看看对不对。。
void dfs(Node* node, int pos, int& left, map>& index){
if (!node) return;
left = left > pos ? pos : left;
if (index.find(pos) == index.end()){
index[pos] = {node->val};
}
else{
index[pos].push_back(node->val);
}
dfs(node->left, pos-1, index);
dfs(node->right, pos+1, index);
}
void printTreeByColumn(Node* root){
map> index;
int left = 0;
dfs(root, 0, left, index);
while (index.find(left) != index.end()){
for (auto& it : index[left]){
cout << it << ", " << endl;
}
cout << endl;
left ++;
}
} |
p****6 发帖数: 724 | |
c*******y 发帖数: 98 | 3 大神说的我无地自容。。
【在 p****6 的大作中提到】 : 这不是新题,出过的。
|
x*******e 发帖数: 84 | 4 可否把题目细说一下?
【在 c*******y 的大作中提到】 : 面筋都是按行打印,今天让我按列打印。手忙脚乱了一阵。。用了个父节点做出来的。 : 电面只写了一道题是不是挂了。。 : 更新题目具体内容: : 按列打印, : a : / \ : b c : / : d : /
|
e********2 发帖数: 495 | 5 这不是Leetcode原题么?
【在 c*******y 的大作中提到】 : 面筋都是按行打印,今天让我按列打印。手忙脚乱了一阵。。用了个父节点做出来的。 : 电面只写了一道题是不是挂了。。 : 更新题目具体内容: : 按列打印, : a : / \ : b c : / : d : /
|
x*******e 发帖数: 84 | 6 啥题目啊?题目细节是啥啊
【在 e********2 的大作中提到】 : 这不是Leetcode原题么?
|
Z**********4 发帖数: 528 | 7 是输出所有的从root到leaf的path嘛?怎么理解按列打印? |
c*******y 发帖数: 98 | |
h*******e 发帖数: 1377 | 9 a
b c
d ef g
输出什么啊。 ef 算一列的么 |
c*******y 发帖数: 98 | 10 f在e左边,不算一列,我更新了一楼
【在 h*******e 的大作中提到】 : a : b c : d ef g : 输出什么啊。 ef 算一列的么
|
|
|
r******y 发帖数: 780 | 11 用一个hashMap来辅助,key是column number, value是一个list.
假设root的col是0,从root开始往下遍历,
左节点如果存在,col为root_col-1, 更新hashmap;
右节点如果存在,col为root_col+1, 更新hashmap;
遍历完,对hashMap的keys排序,然后从小到大输出对应key的每个list
用你的例子测了下,输出OK。 |
r******y 发帖数: 780 | 12 哦,刚发现跟你的思路一样...
应该没撒问题我觉得... |
c*******y 发帖数: 98 | 13 我这是面完了才想到这么做的,之前用了个什么鸟方法根本不对,不能cover所有case
,面试官也没提醒,就过去了。。后来随便画了个别的case才明白过来。。
知道应该move on,但还是很郁闷。
【在 r******y 的大作中提到】 : 哦,刚发现跟你的思路一样... : 应该没撒问题我觉得...
|
p****6 发帖数: 724 | 14 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后
建立一个HashMap, key是index, value是list
贴个java版本的
public List> printVertical1(TreeNode root){
List> res = new ArrayList>();
if(root == null)
return res;
Map> map = new HashMap
TreeNode>>();
getVertical(root, map, 0);
Set keys = new TreeSet(map.keySet());
for(Integer key : keys){
res.add(map.get(key));
}
return res;
}
private void getVertical(TreeNode root, Map> map
, int value){
if(root == null)
return;
if(map.containsKey(value))
map.get(value).add(root);
else{
List list = new ArrayList();
list.add(root);
map.put(value, list);
}
getVertical(root.left, map, value-1);
getVertical(root.right, map, value+1);
} |
r******y 发帖数: 780 | 15 面试总有遇到不nice面试官的可能,不要想太多了。
见到新题的感觉是会不一样的,临场可能会慌,慢慢积累面试经验,相信自己,一定没
问题的。
case
【在 c*******y 的大作中提到】 : 我这是面完了才想到这么做的,之前用了个什么鸟方法根本不对,不能cover所有case : ,面试官也没提醒,就过去了。。后来随便画了个别的case才明白过来。。 : 知道应该move on,但还是很郁闷。
|
g*********e 发帖数: 14401 | |
l*****n 发帖数: 246 | |
p****6 发帖数: 724 | 18 有一个tricky的地方,用java的hashmap记录的话,最后拿到结果的时间复杂度会是
nlog(n), 因为从hashmap里取出来是0,1,2,-1,-2这样非排序的顺序,如果用treeset
去sort才能拿出-2,-1,0,1,2这样的顺序。
对C++ std的map不熟,不知道C++的实现复杂度是多少。 |
w****k 发帖数: 755 | 19 没这么复杂啦,遍历的时候记录最小和最大的col号,输出的时候Hash Key从最小号到
最大号。
treeset
【在 p****6 的大作中提到】 : 有一个tricky的地方,用java的hashmap记录的话,最后拿到结果的时间复杂度会是 : nlog(n), 因为从hashmap里取出来是0,1,2,-1,-2这样非排序的顺序,如果用treeset : 去sort才能拿出-2,-1,0,1,2这样的顺序。 : 对C++ std的map不熟,不知道C++的实现复杂度是多少。
|
p****6 发帖数: 724 | 20
那还不是得排序么?
【在 w****k 的大作中提到】 : 没这么复杂啦,遍历的时候记录最小和最大的col号,输出的时候Hash Key从最小号到 : 最大号。 : : treeset
|
|
|
c********6 发帖数: 33 | 21 不用排序吧,这些col号肯定都是连续的,所以知道边界就可以了 |
l*****a 发帖数: 14598 | 22 人家的意思是:
b的right child是e
c的left child是f
他们怎么算?
【在 c*******y 的大作中提到】 : f在e左边,不算一列,我更新了一楼
|
l*****a 发帖数: 14598 | 23 你这个解法能保证每列的顺序码?
【在 p****6 的大作中提到】 : 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后 : 建立一个HashMap, key是index, value是list : 贴个java版本的 : public List> printVertical1(TreeNode root){ : : List> res = new ArrayList>(); : if(root == null) : return res; : : Map> map = new HashMap
|
r******y 发帖数: 780 | 24 明白waxwak的意思了,就是在遍历的时候track 最小的序号和最大的序号, 也就是例
子里面的-2和2
然后从hashmap里面O(1)查找顺序输出,就不需要排序了
这样就是O(n)而不是O(nlgn).
【在 p****6 的大作中提到】 : : 那还不是得排序么?
|
r******y 发帖数: 780 | 25 我觉得应该是OK的,因为先走的leftmost,tree也不会出现交叉的状况...输出的应该
是这个顺序。
【在 l*****a 的大作中提到】 : 你这个解法能保证每列的顺序码?
|
a*****y 发帖数: 22 | |
l*****a 发帖数: 14598 | 27 先走left,如果走到了右节点的右节点
应该比right先被遍历到吧?
【在 r******y 的大作中提到】 : 我觉得应该是OK的,因为先走的leftmost,tree也不会出现交叉的状况...输出的应该 : 是这个顺序。
|
l*****a 发帖数: 14598 | 28 不是先左后右吗?
【在 a*****y 的大作中提到】 : 先根遍历,可以保证每列都是从上到下的.
|
a*****y 发帖数: 22 | 29 根在孩子的上面,所以先序保证相同的横坐标时,插入map中的list时,纵坐标从上先下排
列.
而先左后右与先右后左没有关系,因为你已经根据左右孩子关系作了减1,加1的横坐标操
作.
不知这样解释可否 |
z*******g 发帖数: 103 | 30 a
/ \
b c
/ /
f d
\ \
g e
\
h
这个例子,会输出 a,h,d吧,还是得keep track of level然后在每个 vertical 的
list里保持高度顺序吧 |
|
|
a*****y 发帖数: 22 | 31 哦,是的.还是需要记录节点的高度的.根据高度作插入排序.
不好意思,考虑得不周全. |
y*******8 发帖数: 112 | 32 其实也不需要用hashmap存放每一列的nodes,因为key空间是连续的,如果最左的列是-
3,最右是2,那么所有的列index就是[-3, -2, -1, 0, 1, 2],用数组存放每一列的
nodes就好了,不用hashmap。
Python的solution请访问
http://codesays.com/2014/solution-to-print-tree-by-columns/
【在 r******y 的大作中提到】 : 明白waxwak的意思了,就是在遍历的时候track 最小的序号和最大的序号, 也就是例 : 子里面的-2和2 : 然后从hashmap里面O(1)查找顺序输出,就不需要排序了 : 这样就是O(n)而不是O(nlgn).
|
m*****k 发帖数: 731 | 33 用treemap
treeset
【在 p****6 的大作中提到】 : 有一个tricky的地方,用java的hashmap记录的话,最后拿到结果的时间复杂度会是 : nlog(n), 因为从hashmap里取出来是0,1,2,-1,-2这样非排序的顺序,如果用treeset : 去sort才能拿出-2,-1,0,1,2这样的顺序。 : 对C++ std的map不熟,不知道C++的实现复杂度是多少。
|
k***g 发帖数: 58 | 34 我只想问,你们加一减一的,对于
A
B C
D E F G
EF属于一列啊,明显不对 |
m*****n 发帖数: 2152 | 35 C++用map插入就是nLog(n),好处是不用排序。
用unordered_map插入式O(n),但是之后要导入sequence container排序,还是nLog(n)。
这题最好的解法应该还是hash table。
不过为了避免rehash,可以traverse tree 一次找出最小和最大的column ID。
然后平移[min, max] -> [0, max-min] (min是负的), root column ID就是-min了。
同vector >(max-min),可以用level traverse tree,插入每个节点,
这样可以保持vertical的顺序。最后O(n) 遍历一下vector,以及下面的list就搞定了。
最后是time complexity 3*n,勉强也算O(n)吧。
treeset
【在 p****6 的大作中提到】 : 有一个tricky的地方,用java的hashmap记录的话,最后拿到结果的时间复杂度会是 : nlog(n), 因为从hashmap里取出来是0,1,2,-1,-2这样非排序的顺序,如果用treeset : 去sort才能拿出-2,-1,0,1,2这样的顺序。 : 对C++ std的map不熟,不知道C++的实现复杂度是多少。
|
l*****f 发帖数: 259 | |
k*****L 发帖数: 55 | 37 我也是电面遇到这个题,挂了。面我的是一个埃及人,很不nice。我开始方向错了,埃
及人不直可否,相反问些无关紧要的细节,浪费我很多时间。比如,假设nodes已经按
column存在hashmap里面了,怎么把它们输出来。他就这样一直扯东扯西。面式快结束
时,我才突然想正确的方法。面试结束后十来分钟,我email他答案,说想知道答案对
不对,他也不回答。
看了FB缺E5的贴子,还说很难招到合格的senior。我想说,按FB这样去面试,能招到就
怪了。假设有两个人,一个人刷过上面的题,一个人从没见过这题,但当场想出来了。
FB显然会让第一个人pass而fail第二个人。
一般水平高的人都有不屑刷题的情绪。刷题极为用功的往往都是水平一般,或转行不久
的人,或new grad 为找到工作没办法。
【在 c*******y 的大作中提到】 : 面筋都是按行打印,今天让我按列打印。手忙脚乱了一阵。。用了个父节点做出来的。 : 电面只写了一道题是不是挂了。。 : 更新题目具体内容: : 按列打印, : a : / \ : b c : / : d : /
|
y*****e 发帖数: 712 | 38 我觉得你说的埃及人就是面我design的人,就是这样,劲儿劲儿的,说啥都不置可否,
错了方向也不告诉你。
我也是电面遇到这个题,挂了。面我的是一个埃及人,很不nice。我开始方向错了,埃
及人不直可否,相反问些无关紧要的细节,浪费我很多时间。比如,假设nodes已经按
column存在........
【在 k*****L 的大作中提到】 : 我也是电面遇到这个题,挂了。面我的是一个埃及人,很不nice。我开始方向错了,埃 : 及人不直可否,相反问些无关紧要的细节,浪费我很多时间。比如,假设nodes已经按 : column存在hashmap里面了,怎么把它们输出来。他就这样一直扯东扯西。面式快结束 : 时,我才突然想正确的方法。面试结束后十来分钟,我email他答案,说想知道答案对 : 不对,他也不回答。 : 看了FB缺E5的贴子,还说很难招到合格的senior。我想说,按FB这样去面试,能招到就 : 怪了。假设有两个人,一个人刷过上面的题,一个人从没见过这题,但当场想出来了。 : FB显然会让第一个人pass而fail第二个人。 : 一般水平高的人都有不屑刷题的情绪。刷题极为用功的往往都是水平一般,或转行不久 : 的人,或new grad 为找到工作没办法。
|
k*****L 发帖数: 55 | 39 爆名字:是不是叫Ahmed Thabet?
【在 y*****e 的大作中提到】 : 我觉得你说的埃及人就是面我design的人,就是这样,劲儿劲儿的,说啥都不置可否, : 错了方向也不告诉你。 : : 我也是电面遇到这个题,挂了。面我的是一个埃及人,很不nice。我开始方向错了,埃 : 及人不直可否,相反问些无关紧要的细节,浪费我很多时间。比如,假设nodes已经按 : column存在........
|
A*******e 发帖数: 2419 | 40 这题目有问题啊。
假设根是0行0列,左走列-1,右走列+1,行数都加1。如果b有右子,那和d的顺序怎么
排?都是2行0列。
【在 c*******y 的大作中提到】 : 面筋都是按行打印,今天让我按列打印。手忙脚乱了一阵。。用了个父节点做出来的。 : 电面只写了一道题是不是挂了。。 : 更新题目具体内容: : 按列打印, : a : / \ : b c : / : d : /
|
|
|
s********a 发帖数: 1447 | 41 bfs按行遍历
然后再 + 1, -1用 vector>记录column值
就可以按列打印 并且 是按tree的顺序了吧~ |
s********a 发帖数: 1447 | |
v*****y 发帖数: 68 | 43 +1,-1应该不对把。应该考虑complete binary tree的情况,只有在leaf那一层,node
之间的列可能是相差1,其余的层,node之间的列一定是大于1的。 |
A*******e 发帖数: 2419 | 44 那就是+2^k,-2^k,k是总层数减当前层数。对最底层,是2^0=1。
对层高为2的完全二叉树,根的列数是0,子节点分别是-2,2,孙节点分别是-3,-1,1
,3。
无非是怎么定义column number。这个向面试官问清楚,实现很简单。
node
【在 v*****y 的大作中提到】 : +1,-1应该不对把。应该考虑complete binary tree的情况,只有在leaf那一层,node : 之间的列可能是相差1,其余的层,node之间的列一定是大于1的。
|