# Tree

## 1. Question

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
• You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 ->NULL
/ \
2 -> 3 ->NULL
/ \ \
4-> 5 -> 7 ->NULL

## 2. Implementation

(1) BFS
public class Solution {
if (root == null) {
return;
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
if (i == size - 1) {
curNode.next = null;
}
else {
curNode.next = queue.peek();
}
if (curNode.left != null) {
}
if (curNode.right != null) {
}
}
}
}
}
(2) Iteration
public class Solution {
TreeLinkNode preNode = null, curNode = root, leftMostNode = null;
while (curNode != null) {
while (curNode != null) {
if (curNode.left != null) {
if (preNode != null) {
preNode.next = curNode.left;
}
else {
leftMostNode = curNode.left;
}
preNode = curNode.left;
}
if (curNode.right != null) {
if (preNode != null) {
preNode.next = curNode.right;
}
else {
leftMostNode = curNode.right;
}
preNode = curNode.right;
}
curNode = curNode.next;
}
curNode = leftMostNode;
preNode = null;
leftMostNode = null;
}
}
}

## 3. Time & Space Complexity

BFS: 时间复杂度: O(n), 空间复杂度: O(w), w是树中拥有最多node的一层中的node个数
Iteration: 时间复杂度: O(n), 空间复杂度: O(1)