116. Populating Next Right Pointers in Each Node
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val,Node _left,Node _right,Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null || root.left == null) {
return root;
}
root.left.next = root.right;
if (root.next != null) {
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
return root;
}
}
另有 BFS 法见下。
117. Populating Next Right Pointers in Each Node II
此方法 116 和 117 通用。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val,Node _left,Node _right,Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Deque<Node> queue = new ArrayDeque<>();
queue.offerLast(root);
while (!queue.isEmpty()) {
Node prev = null;
int size = queue.size();
for (int i = 0; i < size; i++) {
Node cur = queue.pollFirst();
if (prev != null) {
prev.next = cur;
}
prev = cur;
if (cur.left != null) {
queue.offerLast(prev.left);
}
if (cur.right != null) {
queue.offerLast(prev.right);
}
}
}
return root;
}
}