今天去apple store 砸场子# PDA - 掌中宝
c*y
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 ++;
}
}
电面只写了一道题是不是挂了。。
更新题目具体内容:
按列打印,
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
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
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 ++;
}
}