z***m
发帖数: 1602 | 1 问题本身是print a tree in vertical order具体如http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
用hashmap很好解决
问题来了，follow up要one pass (不能找最左有多远，最右有多远)， 不要hashmap |
b******n
发帖数: 851 | 2 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去 |
z***m
发帖数: 1602 | 3 我见过的解法，不管是DFS还是用hash的，都需要run一次多余的求最左最右的范围，如
果不让求的话，感觉有点难。 |
s********l
发帖数: 998 | 4 你在国内 还是美国啊？
为什么总被 老中面
我怎么没这种事呢~
【在 b******n 的大作中提到】
: 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
|
b******n
发帖数: 851 | 5 我去他妈的twitter面， 四五轮， 反正有三个老中， 把我拒了。 我也不是特别好，
但也不是特别差。。。 一个twitter老中， 看我简历， 还他妈的婉转的说， 你毕业
好多年了啊。。。 意思是， 你年纪好大啊
我去pure storage， 一道iterator和那个processtask的那题， 两个老中， 从
microsoft出来的，一个iterator， 做的一点都没错。 那个process task的题，
unlock没写的最optimal。 然后第二天就说move on
反正如果你不是猥琐男， 或者刚毕业的新鲜中国女逼， 遇到老中， 别想过!
【在 s********l 的大作中提到】
: 你在国内 还是美国啊？
: 为什么总被 老中面
: 我怎么没这种事呢~
|
b******n
发帖数: 851 | 6 void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);
helper(node.left, m, level-1);
helper(node.right, m, level+1);
} |
p*********g
发帖数: 116 | 7 这不还是map 的解法吗？
【在 b******n 的大作中提到】
: void helper (TreeNode node, TreeMap m, int level) {
: List nodesAtThisLevel = m.get(level);
: if (nodesAtThisLevel == null) ...
: nodesAtThisLevel.add(node);
:
: helper(node.left, m, level-1);
: helper(node.right, m, level+1);
: }
|
p*********g
发帖数: 116 | 8 我想起来了， 用双向链表。
左子树就向左走，右子树就向右走。 走到头就创建新节点。
不知道对不对？ |
h*******0
发帖数: 270 | 9 目测正确
【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
|
z***m
发帖数: 1602 | 10 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
啊。
估计被烙印带阴沟。
【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
|
|
|
w****u
发帖数: 3147 | |
k*******n
发帖数: 190 | 12 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
PrintPath();
path.removeElement(curNode);
};
} |
z***m
发帖数: 1602 | 13 你这是在打印所有root到path的节点吧，vertical print不是这个意思。
还是谢谢你的code。
【在 k*******n 的大作中提到】
: public class BinaryTree {
: TreeNode root;
: Vector path;
:
: public void FindPath() {
: if (root!=null) FindPath(root);
: };
: public void FindPath(TreeNode curNode) {
: boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
: if (!isLeaf) {
|
g*****y
发帖数: 94 | 14 Follow up 如何做？有人能够详细解释下么？ |
w******e
发帖数: 3 | 15 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定 |
g*****y
发帖数: 94 | 16 我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。
【在 w******e 的大作中提到】
: 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
|
k****r
发帖数: 807 | 17 recursive，
用list《List《Integer》》 res纪录结果，
用一个mostleft记录目前最左边的index，
如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
static int mostLeft = 0;
public static void printTreeInVerticalOrder(TreeNode root) {
List> res = new ArrayList<>();
//res.add(new ArrayList());
printHelper(root, 0, res);
printTree(res);
}
public static void printHelper(TreeNode root, int curr, List
Integer>> res) {
if (root == null) return;
else if (curr < mostLeft) {
List list = new ArrayList<>();
list.add(root.val);
res.add(0, list);
mostLeft = curr;
} else if (curr - mostLeft >= res.size()) {
List list = new ArrayList<>();
list.add(root.val);
res.add(list);
} else {
int idx = curr - mostLeft;
List list = res.get(idx);
list.add(root.val);
}
printHelper(root.left, curr - 1, res);
printHelper(root.right, curr + 1, res);
}
public static void printTree(List> res) {
for (List list : res) {
for (Integer i : list) {
System.out.print(i + ",");
}
System.out.println();
}
} |
b******b
发帖数: 713 | 18 I feel "cannot use hashmap" is an unnecessary constraint. we will need a
container to store the values anyway (cannot think up a way without use a
container), use hashmap or list of list really doesn't make much difference,
hashmap actually is faster, list of list won't buy you anything, cpu or
memory.
【在 k****r 的大作中提到】
: recursive，
: 用list《List《Integer》》 res纪录结果，
: 用一个mostleft记录目前最左边的index，
: 如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
: static int mostLeft = 0;
: public static void printTreeInVerticalOrder(TreeNode root) {
: List> res = new ArrayList<>();
: //res.add(new ArrayList());
: printHelper(root, 0, res);
: printTree(res);
|
k****r
发帖数: 807 | 19 hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
list of list多用了点memory ：）
difference,
【在 b******b 的大作中提到】
: I feel "cannot use hashmap" is an unnecessary constraint. we will need a
: container to store the values anyway (cannot think up a way without use a
: container), use hashmap or list of list really doesn't make much difference,
: hashmap actually is faster, list of list won't buy you anything, cpu or
: memory.
|
b******b
发帖数: 713 | 20 yeah, that's what i'm thinking, hashmap is HashMap>, it'
s almost same as the code in previous post, except use the level as index.
【在 k****r 的大作中提到】
: hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
: list of list多用了点memory ：）
:
: difference,
|
|
|
g*****y
发帖数: 94 | 21 我感觉也是，这个constraint应该是没有必要的。
it'
【在 b******b 的大作中提到】
: yeah, that's what i'm thinking, hashmap is HashMap>, it'
: s almost same as the code in previous post, except use the level as index.
|
T****U
发帖数: 3344 | 22 这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 20);
root = insert(root, 70);
root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 7);
root = insert(root, 80);
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, 0);
VerticalOrder(root, 0);
cout <<"hn";
int i, j;
//printing first half
for(i = 100; i >= 0; i--) {
int flag = 0;
for(j = 0; j < v1[i].size(); j++) {
cout << v1[i][j] <<" ";
flag = 1;
}
if(flag == 1)
cout << endl;
}
// printing second half
for(i = 0; i < 100; i++) {
int flag = 0;
for(j = 0; j < v2[i].size(); j++) {
cout << v2[i][j] <<" ";
flag = 1;
}
if(flag == 1)
cout << endl;
}
}
onepass
【在 z***m 的大作中提到】
: 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
: 啊。
: 估计被烙印带阴沟。
|
t*******e
发帖数: 274 | 23 这个用java 怎么改写？
【在 T****U 的大作中提到】
: 这应该是烙印的版本，给两个100的vectors
: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 后面问答区一个烙印贴的
: vector v1[100];
: vector v2[100];
: void VerticalOrder(struct BstNode* root, int index) {
: if(!root) return;
: if(index < 0) {
: v1[-1*index].push_back(root->data);
: }
|
z***m
发帖数: 1602 | 24 问题本身是print a tree in vertical order具体如http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
用hashmap很好解决
问题来了，follow up要one pass (不能找最左有多远，最右有多远)， 不要hashmap |
b******n
发帖数: 851 | 25 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去 |
z***m
发帖数: 1602 | 26 我见过的解法，不管是DFS还是用hash的，都需要run一次多余的求最左最右的范围，如
果不让求的话，感觉有点难。 |
s********l
发帖数: 998 | 27 你在国内 还是美国啊？
为什么总被 老中面
我怎么没这种事呢~
【在 b******n 的大作中提到】
: 想想， 一天到晚被中国猥琐男女面试时， 不放水。。自己查去
|
b******n
发帖数: 851 | 28 我去他妈的twitter面， 四五轮， 反正有三个老中， 把我拒了。 我也不是特别好，
但也不是特别差。。。 一个twitter老中， 看我简历， 还他妈的婉转的说， 你毕业
好多年了啊。。。 意思是， 你年纪好大啊
我去pure storage， 一道iterator和那个processtask的那题， 两个老中， 从
microsoft出来的，一个iterator， 做的一点都没错。 那个process task的题，
unlock没写的最optimal。 然后第二天就说move on
反正如果你不是猥琐男， 或者刚毕业的新鲜中国女逼， 遇到老中， 别想过!
【在 s********l 的大作中提到】
: 你在国内 还是美国啊？
: 为什么总被 老中面
: 我怎么没这种事呢~
|
b******n
发帖数: 851 | 29 void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);
helper(node.left, m, level-1);
helper(node.right, m, level+1);
} |
p*********g
发帖数: 116 | 30 这不还是map 的解法吗？
【在 b******n 的大作中提到】
: void helper (TreeNode node, TreeMap m, int level) {
: List nodesAtThisLevel = m.get(level);
: if (nodesAtThisLevel == null) ...
: nodesAtThisLevel.add(node);
:
: helper(node.left, m, level-1);
: helper(node.right, m, level+1);
: }
|
|
|
p*********g
发帖数: 116 | 31 我想起来了， 用双向链表。
左子树就向左走，右子树就向右走。 走到头就创建新节点。
不知道对不对？ |
h*******0
发帖数: 270 | 32 目测正确
【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
|
z***m
发帖数: 1602 | 33 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
啊。
估计被烙印带阴沟。
【在 p*********g 的大作中提到】
: 我想起来了， 用双向链表。
: 左子树就向左走，右子树就向右走。 走到头就创建新节点。
: 不知道对不对？
|
w****u
发帖数: 3147 | |
k*******n
发帖数: 190 | 35 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
PrintPath();
path.removeElement(curNode);
};
} |
z***m
发帖数: 1602 | 36 你这是在打印所有root到path的节点吧，vertical print不是这个意思。
还是谢谢你的code。
【在 k*******n 的大作中提到】
: public class BinaryTree {
: TreeNode root;
: Vector path;
:
: public void FindPath() {
: if (root!=null) FindPath(root);
: };
: public void FindPath(TreeNode curNode) {
: boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
: if (!isLeaf) {
|
g*****y
发帖数: 94 | 37 Follow up 如何做？有人能够详细解释下么？ |
w******e
发帖数: 3 | 38 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定 |
g*****y
发帖数: 94 | 39 我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。
【在 w******e 的大作中提到】
: 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定
|
k****r
发帖数: 807 | 40 recursive，
用list《List《Integer》》 res纪录结果，
用一个mostleft记录目前最左边的index，
如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
static int mostLeft = 0;
public static void printTreeInVerticalOrder(TreeNode root) {
List> res = new ArrayList<>();
//res.add(new ArrayList());
printHelper(root, 0, res);
printTree(res);
}
public static void printHelper(TreeNode root, int curr, List
Integer>> res) {
if (root == null) return;
else if (curr < mostLeft) {
List list = new ArrayList<>();
list.add(root.val);
res.add(0, list);
mostLeft = curr;
} else if (curr - mostLeft >= res.size()) {
List list = new ArrayList<>();
list.add(root.val);
res.add(list);
} else {
int idx = curr - mostLeft;
List list = res.get(idx);
list.add(root.val);
}
printHelper(root.left, curr - 1, res);
printHelper(root.right, curr + 1, res);
}
public static void printTree(List> res) {
for (List list : res) {
for (Integer i : list) {
System.out.print(i + ",");
}
System.out.println();
}
} |
|
|
b******b
发帖数: 713 | 41 I feel "cannot use hashmap" is an unnecessary constraint. we will need a
container to store the values anyway (cannot think up a way without use a
container), use hashmap or list of list really doesn't make much difference,
hashmap actually is faster, list of list won't buy you anything, cpu or
memory.
【在 k****r 的大作中提到】
: recursive，
: 用list《List《Integer》》 res纪录结果，
: 用一个mostleft记录目前最左边的index，
: 如果目前level小于mostleft，or超出res大小，插最前面，或最后面新的list：
: static int mostLeft = 0;
: public static void printTreeInVerticalOrder(TreeNode root) {
: List> res = new ArrayList<>();
: //res.add(new ArrayList());
: printHelper(root, 0, res);
: printTree(res);
|
k****r
发帖数: 807 | 42 hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
list of list多用了点memory ：）
difference,
【在 b******b 的大作中提到】
: I feel "cannot use hashmap" is an unnecessary constraint. we will need a
: container to store the values anyway (cannot think up a way without use a
: container), use hashmap or list of list really doesn't make much difference,
: hashmap actually is faster, list of list won't buy you anything, cpu or
: memory.
|
b******b
发帖数: 713 | 43 yeah, that's what i'm thinking, hashmap is HashMap>, it'
s almost same as the code in previous post, except use the level as index.
【在 k****r 的大作中提到】
: hashmap咋做我还真没仔细想。。。。是用一个level num当index key吗？那样好像比
: list of list多用了点memory ：）
:
: difference,
|
g*****y
发帖数: 94 | 44 我感觉也是，这个constraint应该是没有必要的。
it'
【在 b******b 的大作中提到】
: yeah, that's what i'm thinking, hashmap is HashMap>, it'
: s almost same as the code in previous post, except use the level as index.
|
T****U
发帖数: 3344 | 45 这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 20);
root = insert(root, 70);
root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 7);
root = insert(root, 80);
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, 0);
VerticalOrder(root, 0);
cout <<"hn";
int i, j;
//printing first half
for(i = 100; i >= 0; i--) {
int flag = 0;
for(j = 0; j < v1[i].size(); j++) {
cout << v1[i][j] <<" ";
flag = 1;
}
if(flag == 1)
cout << endl;
}
// printing second half
for(i = 0; i < 100; i++) {
int flag = 0;
for(j = 0; j < v2[i].size(); j++) {
cout << v2[i][j] <<" ";
flag = 1;
}
if(flag == 1)
cout << endl;
}
}
onepass
【在 z***m 的大作中提到】
: 烙印提示说用一个vector。如果是用vector，就得知道node的数目，那就不能onepass
: 啊。
: 估计被烙印带阴沟。
|
t*******e
发帖数: 274 | 46 这个用java 怎么改写？
【在 T****U 的大作中提到】
: 这应该是烙印的版本，给两个100的vectors
: http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 后面问答区一个烙印贴的
: vector v1[100];
: vector v2[100];
: void VerticalOrder(struct BstNode* root, int index) {
: if(!root) return;
: if(index < 0) {
: v1[-1*index].push_back(root->data);
: }
|
p******n
发帖数: 185 | 47 two vector, leftside and rightside of the root
traverse one pass
【在 z***m 的大作中提到】
: 问题本身是print a tree in vertical order具体如http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
: 用hashmap很好解决
: 问题来了，follow up要one pass (不能找最左有多远，最右有多远)， 不要hashmap
|
