三刷 06/2022
有一个逻辑是每次向下走一层的时候都要重置nextParentHead node，但是又要用到这个点，所以没有办法在上一层就清空
我自己的做法是用了一个do while的循环 -> 又看了一下之前写的答案发现可以在上层循环的最后update parentPointer，所以do while也不是很有必要
看了答案有一个很巧妙的方法是清空prev node，如果prev node是null就证明现在这个点是当前层的第一个点就可以把它当成nextParentHead
另外答案写的好的一个地方就是把重复的code单拎出来写了一个processChild减少了重复代码，不过这样需要一些全局变量，所以也有一些trade off
Time O(N)
Space O(1)
Runtime: 1 ms, faster than 74.94% of Java online submissions for Populating Next Right Pointers in Each Node II.
Memory Usage: 45.3 MB, less than 23.77% of Java online submissions for Populating Next Right Pointers in Each Node II.
class Solution {
public Node connect(Node root) {
// parent 1
// curr 2 3
Node nextParentHead = root;
Node parentPointer = null;
Node currPrev = null, curr = null;
do {
parentPointer = nextParentHead;
nextParentHead = null;
currPrev = null;
while (parentPointer != null) {
if (parentPointer.left != null) {
curr = parentPointer.left;
if (nextParentHead == null) {
nextParentHead = curr;
}
if (currPrev != null) {
currPrev.next = curr;
}
currPrev = curr;
}
if (parentPointer.right != null) {
curr = parentPointer.right;
if (nextParentHead == null) {
nextParentHead = curr;
}
if (currPrev != null) {
currPrev.next = curr;
}
currPrev = curr;
}
parentPointer = parentPointer.next;
}
} while (nextParentHead != null);
return root;
}
}
16.70 %
Version #1
一刷
不用Queue的Level Order Traversal
41.24 %
public class Solution {
public void connect(TreeLinkNode root) {
/*
1
/ \
2 3
/ \ \
4 5 7
*/
TreeLinkNode curr = null;
TreeLinkNode childHead = null;
TreeLinkNode childCurr = null;
curr = root;
while (curr != null) {
childHead = null;
// level
while (curr != null) {
if (curr.left != null) {
if (childHead == null) {
childHead = curr.left;
childCurr = childHead;
} else {
childCurr.next = curr.left;
childCurr = childCurr.next;
}
}
if (curr.right != null) {
if (childHead == null) {
childHead = curr.right;
childCurr = childHead;
} else {
childCurr.next = curr.right;
childCurr = childCurr.next;
}
}
curr = curr.next;
}
// level ends -> curr goes to the next level's head
curr = childHead;
}
}
}
不用Queue的Level Order Traversal
41.24 %
public class Solution {
public void connect(TreeLinkNode root) {
/*
1
/ \
2 3
/ \ \
4 5 7
*/
TreeLinkNode curr = null;
TreeLinkNode childHead = null;
TreeLinkNode childCurr = null;
curr = root;
while (curr != null) {
childHead = null;
// level
while (curr != null) {
if (curr.left != null) {
if (childHead == null) {
childHead = curr.left;
childCurr = childHead;
} else {
childCurr.next = curr.left;
childCurr = childCurr.next;
}
}
if (curr.right != null) {
if (childHead == null) {
childHead = curr.right;
childCurr = childHead;
} else {
childCurr.next = curr.right;
childCurr = childCurr.next;
}
}
curr = curr.next;
}
// level ends -> curr goes to the next level's head
curr = childHead;
}
}
}
二刷
写的时候卡住了一下，主要是nested while loop的条件想得不好
和116是一样的pattern
Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II.
Memory Usage: 38.3 MB, less than 92.61% of Java online submissions for Populating Next Right Pointers in Each Node II.
class Solution {
public Node connect(Node root) {
// a
// /\
// b->c
// /\ \
// d->-> f
Node parent = root;
Node levelHead = null;
Node prev = null;
while (parent != null) {
levelHead = null;
prev = null;
while (parent != null) {
if (parent.left != null) {
if (levelHead == null) {
levelHead = parent.left;
}
if (prev != null) {
prev.next = parent.left;
}
prev = parent.left;
}
if (parent.right != null) {
if (levelHead == null) {
levelHead = parent.right;
}
if (prev != null) {
prev.next = parent.right;
}
prev = parent.right;
}
parent = parent.next;
}
parent = levelHead;
}
return root;
}
}
Version #2 with Queue
（二刷note：题目要求O(1) space所以这个方法是不成立的）
53.66 %
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.offer(root);
TreeLinkNode prev = null;
TreeLinkNode curr = null;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
curr = queue.poll();
if (prev != null) {
prev.next = curr;
}
prev = curr;
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}
prev = null;
}
}
}
53.66 %
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.offer(root);
TreeLinkNode prev = null;
TreeLinkNode curr = null;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
curr = queue.poll();
if (prev != null) {
prev.next = curr;
}
prev = curr;
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}
prev = null;
}
}
}
No comments:
Post a Comment