w*****h
发帖数: 423 | 1 一个tree，每个节点只有指向父亲的指针（传统的树是指向儿子的指针）
然后一个array存储了tree的每个节点
一个例子
A
B C
D E F G
根据这个array, 打印出如下序列
A
->B
->->D
->->E
->C
->->F
->->G |
j**7
发帖数: 143 | 2 没有测试过
public void paintNodes(TreeNode[] nodes) {
for (TreeNode n : nodes) {
TreeNode current = n;
while (current.parent != null) {
System.out.print("->");
current = current.parent;
}
System.out.println(n.c);
}
}
public class TreeNode {
char c;
TreeNode parent;
public TreeNode() {
}
} |
b**********5
发帖数: 7881 | 3 结果没排序。。。
【在 j**7 的大作中提到】
: 没有测试过
: public void paintNodes(TreeNode[] nodes) {
: for (TreeNode n : nodes) {
: TreeNode current = n;
: while (current.parent != null) {
: System.out.print("->");
: current = current.parent;
: }
: System.out.println(n.c);
: }
|
r*g
发帖数: 186 | 4 没想到什么好的办法
【在 w*****h 的大作中提到】
: 一个tree，每个节点只有指向父亲的指针（传统的树是指向儿子的指针）
: 然后一个array存储了tree的每个节点
: 一个例子
: A
: B C
: D E F G
: 根据这个array, 打印出如下序列
: A
: ->B
: ->->D
|
w*****h
发帖数: 423 | 5 这个肯定不行，需要按照我那个例子的顺序， post traverse
【在 j**7 的大作中提到】
: 没有测试过
: public void paintNodes(TreeNode[] nodes) {
: for (TreeNode n : nodes) {
: TreeNode current = n;
: while (current.parent != null) {
: System.out.print("->");
: current = current.parent;
: }
: System.out.println(n.c);
: }
|
n******n
发帖数: 12088 | 6 先重建树不行吗？
【在 w*****h 的大作中提到】
: 这个肯定不行，需要按照我那个例子的顺序， post traverse
|
l*****a
发帖数: 14598 | 7 construct a map as
Map>
【在 w*****h 的大作中提到】
: 一个tree，每个节点只有指向父亲的指针（传统的树是指向儿子的指针）
: 然后一个array存储了tree的每个节点
: 一个例子
: A
: B C
: D E F G
: 根据这个array, 打印出如下序列
: A
: ->B
: ->->D
|
s******x
发帖数: 417 | 8 //建立map
Map> map = new Map>();
ArrayList childrenList = new ArrayList();
map.set(array[0], childrenList);
for(int i = 1; i < array.length; i ++)
{
if(map.contains(array[i].parent)
{
ArrayList temp = map.get(array[i].parent);
temp.add(array[i]);
}
else
{
ArrayList newchildrenList = new ArrayList();
newChildrenList.add(array[i]);
map.set(array[i], newChildrenList);
}
}
//深搜
public void DFS(Node root, int level)
{
// write your code here
int i = level;
while(i > 0)
{
print("->");
i --;
}
print(root.val);
ArrayList children = map.get(root);
if(children.size() > 0)
{
for(Node child : children)
{
DFS(child, level + 1);
}
}
else
{
return
}
}
【在 l*****a 的大作中提到】
: construct a map as
: Map>
|
l*****a
发帖数: 14598 | 9 map already contains the parent/children relationship
then just do a DFS
what does stack use for?
【在 s******x 的大作中提到】
: //建立map
: Map> map = new Map>();
: ArrayList childrenList = new ArrayList();
: map.set(array[0], childrenList);
: for(int i = 1; i < array.length; i ++)
: {
: if(map.contains(array[i].parent)
: {
: ArrayList temp = map.get(array[i].parent);
: temp.add(array[i]);
|
s******x
发帖数: 417 | 10 不需要stack，我已经修改。
【在 l*****a 的大作中提到】
: map already contains the parent/children relationship
: then just do a DFS
: what does stack use for?
|
|
|
l*****a
发帖数: 14598 | 11 你这java是自学的？
【在 s******x 的大作中提到】
: 不需要stack，我已经修改。
|
l*****a
发帖数: 14598 | 12 array[0] may not be root
u need to handle root seperately
【在 s******x 的大作中提到】
: //建立map
: Map> map = new Map>();
: ArrayList childrenList = new ArrayList();
: map.set(array[0], childrenList);
: for(int i = 1; i < array.length; i ++)
: {
: if(map.contains(array[i].parent)
: {
: ArrayList temp = map.get(array[i].parent);
: temp.add(array[i]);
|
s******x
发帖数: 417 | 13 大师慧眼。
【在 l*****a 的大作中提到】
: 你这java是自学的？
|
l*****a
发帖数: 14598 | 14 你装个eclipse什么的看看让不让你compile
【在 s******x 的大作中提到】
: 大师慧眼。
|
s******x
发帖数: 417 | 15 也对。
那就在建立map的时候，如果parent 是null，那就是root，就行了。我只是简单认为0
是root而已，就是意思意思罢了。面试这样就挂了。。
【在 l*****a 的大作中提到】
: array[0] may not be root
: u need to handle root seperately
|
s******x
发帖数: 417 | 16 不是leetcode或者lintcode，我这里就是大概写个意思。
你说的无法compile的错误，能指出来吗？
【在 l*****a 的大作中提到】
: 你装个eclipse什么的看看让不让你compile
|
s******x
发帖数: 417 | 17 难道是HashMap写成Map?呵呵，大概意思齐了，都快深夜了，真没心力去深究。：（ |
y**i
发帖数: 1112 | 18 拓扑排序的逆序吧
【在 w*****h 的大作中提到】
: 一个tree，每个节点只有指向父亲的指针（传统的树是指向儿子的指针）
: 然后一个array存储了tree的每个节点
: 一个例子
: A
: B C
: D E F G
: 根据这个array, 打印出如下序列
: A
: ->B
: ->->D
|
n******n
发帖数: 12088 | 19 自己编译一下不就知道了？兴致勃勃地贴代码，也得保证质量啊。看代码很费时间的。
【在 s******x 的大作中提到】
: 不是leetcode或者lintcode，我这里就是大概写个意思。
: 你说的无法compile的错误，能指出来吗？
|
n******n
发帖数: 12088 | 20 这题目没说清楚，左右子节点无法区分，只能假定先看到的是左，后者则是右。
【在 y**i 的大作中提到】
: 拓扑排序的逆序吧
|
