-
Notifications
You must be signed in to change notification settings - Fork 1
/
PopulatingNextRightPointersEachNode.java
86 lines (73 loc) · 2.5 KB
/
PopulatingNextRightPointersEachNode.java
1
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
package com.leetcode;
import java.util.LinkedList;
import java.util.Queue;
public class PopulatingNextRightPointersEachNode {
//https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
/* last level contains N/2 nodes. The space complexity for breadth first traversal
is the maximum space occupied and the space occupied by the queue is dependent upon the
maximum number of nodes in particular level.
So, in this case, the space complexity would be O(N)O(N).
*/
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(queue.size() >0){
LinkedList<Node> level = new LinkedList<>();
while(queue.size() > 0){
Node node = queue.poll();
if(queue.size() > 0){
node.next = queue.peek();
}
if(node.left != null) level.add(node.left);
if(node.right != null) level.add(node.right);
}
//for(int i = 0 ; i < level.size() -1 ; i++){
// Node n = level.get(i);
// n.next = level.get(i+1);
//}
queue = level;
}
return root;
}
}
//Optimized memory
class Solution2 {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(queue.size() >0){
int size = queue.size();
while(size > 0){
Node node = queue.poll();
size--;
if(size > 0){
node.next = queue.peek();
}
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
return root;
}
}
// 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;
}
};
}