populating next right pointers in each node


Populating Next Right Pointers in Each Node
一次过了之后,不理解为啥这题会被标记为medium。后来仔细一看,要求contant space!下面这个naive的方法不符合题意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void (TreeLinkNode root) {
if (root == null)
return;
List<TreeLinkNode> parents = new LinkedList<TreeLinkNode>();
parents.add(root);
while (parents.size() > 0) {
for (int i = 0; i < parents.size() - 1; ++i) {
parents.get(i).next = parents.get(i + 1);
}
List<TreeLinkNode> children = new LinkedList<TreeLinkNode>();
for (TreeLinkNode node : parents) {
if (node.left != null)
children.add(node.left);
if (node.right != null)
children.add(node.right);
}
parents = children;
}
}