ARTS Week 13

Algorithm
This week’s LeetCode problem is 116. Populating Next Right Pointers in Each Node
Description: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
. Initially, all next pointers are set to NULL
.
The first idea is to use a hierarchical traversal, and just join the results of the hierarchical traversal with the next
pointer. Code omitted
The second way is that finding the next
pointer, we can find that there are two types of cases, the first one is that it belongs to the same parent node, then the next
pointer of the left node is pointing to the right node, i.e. root.left.next = root.right
; the second one is that it does not belong to the same parent node, then the next
pointer of this node is the left child of the next node of its parent, i.e. root.right. node's next node's left child, i.e. root.right.next = root.next.left
. The accepted code is as follows.
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
} Node left = root;
while (left.left != null) {
Node curr = left;
while (curr != null) {
curr.left.next = curr.right;
curr.right.next = (curr.next != null) ? curr.next.left : null;
curr = curr.next;
}
left = left.left;
} return root;
}
}
Review
This week’s Review is for the following article: Think Different. Think Users.
In this essay, author offers four points about thinking differently.
- You’ll need to be prepared to do it.
- You shouldn’t just do it gratuitously; You should do it in the course of serving users.
- If you make those users happy, it will give you the strength to resist the force of convention.
- The gap between users’ view of you and the outside world’s view of you is a sign of your potential.
Tip
Difference between Arrays.sort()
and Collections.sort()
in Java: Arrays.sort()
: used to sort arrays such as int []
.
Arrays.sort()
: used to sort arrays, e.g.int []
Collections.sort()
: used to sort lists, e.g.List<Integer>
Here is a sample.
public class Main {
public static void main(String[] args) {
int[] arr = {2,4,3,1};
Arrays.sort(arr);
List<Integer> list = new ArrayList<>();
list.add(2);
list.add(4);
list.add(3);
list.add(1);
Collections.sort(list)。
}
}
Share
I’ve recently started to read OSTEP(Operating Systems: Three Easy Pieces) seriously, and I’m doing the post-course exercises, and I should be sharing the answers on my blog later.