三刷 06/2022
Version #1 BFS
看了题目的constraint，要求O(1) extra space，所以这个方法是不可行的
Time O(N)
Space O(N)
Runtime: 3 ms, faster than 44.31% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 48.2 MB, less than 10.30% of Java online submissions for Populating Next Right Pointers in Each Node.
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> que = new ArrayDeque<>();
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
Node prev = null;
while (size-- > 0) {
Node curr = que.poll();
if (prev != null) {
prev.next = curr;
}
if (curr.left != null) {
que.offer(curr.left);
}
if (curr.right != null) {
que.offer(curr.right);
}
prev = curr;
}
}
return root;
}
}
Version #2 Add hoc method with constant space
Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 47.1 MB, less than 62.18% of Java online submissions for Populating Next Right Pointers in Each Node.
Time O(N)
Space O(1)
class Solution {
public Node connect(Node root) {
// Maitain a head node as the left most node of each level
Node head = root;
while (head != null) {
Node curr = head;
if (curr.left == null) {
break;
}
while (curr != null) {
// Reach the leaf of the tree
curr.left.next = curr.right;
if (curr.next != null) {
curr.right.next = curr.next.left;
}
curr = curr.next;
}
head = head.left;
}
return root;
}
}
Version #1 套用level order traversal 模板
Time O(n)
Space O(n)
写High了忘了加left和right children
非常需要注意
18.95 %
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode prev = null;
TreeLinkNode curr;
int size;
Queue<TreeLinkNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
size = que.size();
while (size-- > 0) {
curr = que.poll();
if (prev != null) {
prev.next = curr;
}
prev = curr;
if (curr.left != null) que.offer(curr.left);
if (curr.right != null) que.offer(curr.right);
}
prev.next = null;
prev = null;
}
}
}
二刷
Runtime: 1 ms, faster than 57.79% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 39.1 MB, less than 70.19% of Java online submissions for Populating Next Right Pointers in Each Node.
class Solution {
public Node connect(Node root) {
// a
// /\
// b -> c -> NULL
if (root == null) {
return root;
}
Queue<Node> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
Node prev = null;
while (size-- > 0) {
Node curr = que.poll();
if (prev != null) {
prev.next = curr;
}
if (curr.left != null) {
que.offer(curr.left);
que.offer(curr.right);
}
prev = curr;
}
}
return root;
}
}
Version #2 Better solution
看了LC上答案，可以不用queue，做到O(1)space
Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 38.5 MB, less than 99.89% of Java online submissions for Populating Next Right Pointers in Each Node.
class Solution {
public Node connect(Node root) {
// a -> NULL
// /\
// b -> c -> NULL
// /\ /\
// d->e->f->g-> NULL
Node curr = root;
while (curr != null) {
Node head = curr;
while (curr != null) {
if (curr.left != null) {
curr.left.next = curr.right;
}
if (curr.right != null && curr.next != null) {
curr.right.next = curr.next.left;
}
curr = curr.next;
}
curr = head.left;
}
return root;
}
}
No comments:
Post a Comment