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.

  1. You’ll need to be prepared to do it.
  2. You shouldn’t just do it gratuitously; You should do it in the course of serving users.
  3. If you make those users happy, it will give you the strength to resist the force of convention.
  4. 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
KeepNewbie_yan

KeepNewbie_yan

A programmer. Share knowledge of programming, operating system, Linux kernel, and reading, thinking etc. Let us maintain a beginner mend and grow together!