https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
my solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public Node connect(Node root) {
if(root==null) return null;
LinkedList<Node> ls=new LinkedList<>();
ls.offer(root);
while(!ls.isEmpty()){
if(is_2(ls.size())){
for(int i=0;i<ls.size()-1;i++){
ls.get(i).next=ls.get(i+1);
}
}
Node newNode=ls.poll();
if(newNode.left!=null){
ls.offer(newNode.left);
}
if(newNode.right!=null){
ls.offer(newNode.right);
}
}
return root;
}
public boolean is_2(int a){
if((a&(a-1))==0) return true;
return false;
}
}
leetcode solutions1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
class Solution_1 {
public Node connect(Node root) {
if (root == null) {
return root;
}
// Initialize a queue data structure which contains
// just the root of the tree
Queue<Node> Q = new LinkedList<Node>();
Q.add(root);
// Outer while loop which iterates over
// each level
while (Q.size() > 0) {
// Note the size of the queue
int size = Q.size();
// ---> ** Iterate over all the nodes on the current level ** <---
for (int i = 0; i < size; i++) {
// Pop a node from the front of the queue
Node node = Q.poll();
// This check is important. We don't want to
// establish any wrong connections. The queue will
// contain nodes from 2 levels at most at any
// point in time. This check ensures we only
// don't establish next pointers beyond the end
// of a level
if (i < size - 1) {
node.next = Q.peek();
}
// Add the children, if any, to the back of
// the queue
if (node.left != null) {
Q.add(node.left);
}
if (node.right != null) {
Q.add(node.right);
}
}
}
// Since the tree has now been modified, return the root node
return root;
}
}
class Solution_2 {
public Node connect(Node root) {
if (root == null) {
return root;
}
// Start with the root node. There are no next pointers
// that need to be set up on the first level
Node leftmost = root;
// Once we reach the final level, we are done
while (leftmost.left != null) {
// Iterate the "linked list" starting from the head
// node and using the next pointers, establish the
// corresponding links for the next level
Node head = leftmost;
while (head != null) {
// CONNECTION 1
head.left.next = head.right;
// CONNECTION 2
if (head.next != null) {
head.right.next = head.next.left;
}
// Progress along the list (nodes on the current level)
head = head.next;
}
// Move onto the next level
leftmost = leftmost.left;
}
return root;
}
}