116&117. Populating Next Right Pointers in Each Node I & II
116. Populating Next Right Pointers in Each Node
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.
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.Example 2:
Input: root = []
Output: []Constraints:
The number of nodes in the tree is in the range
[0, 212 - 1].-1000 <= Node.val <= 1000
Follow-up:
You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
My Solutions:
方法1: BFS - Right to Left
It's important to see that the given tree is a perfect binary tree. This means that each node will always have both children and only the last level of nodes will have no children.
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
Node rightNode = null;
for(int i = q.size(); i > 0; i--) {
Node cur = q.poll();
cur.next = rightNode;
rightNode = cur;
if(cur.right != null) {
q.offer(cur.right); // 先加right，后加left
q.offer(cur.left);
}
}
}
return root;
}Time: O(N);
Space: O(w), where w is the width of tree. This is required to store the nodes in queue. Since the given tree is a perfect binary tree, its width is given as W=(N+1)/2
方法2: DFS
In DFS, once we go to the next level, we can't get access to right node. So, we must update next pointers of the child of each node from the its parent's level itself.
public Node connect(Node root) {
if (root == null) return null;
Node L = root.left, R = root.right, N = root.next;
if (L != null) { // if child node exists
L.next = R; // if L child exists, R child must exist
if (N != null) R.next = N.left; // assign R's next to be root's next's left
connect(L);
connect(R);
}
return root;
}Time: O(N);
Space: O(logN), required for recursive stack. The maximum depth of recursion is equal to the height of tree which in this case of perfect binary tree is equal to O(logN)
方法3: BFS - Space-Optimized
This is a combination of logic of above logics- we will traverse in BFS manner but populate the next pointers of bottom level just as we did in the DFS solution.d from root's left.
public Node connect(Node root) {
Node head = root;
// iterate each level of tree
for(; root != null; root = root.left)
// iterate each node in a level
for(Node cur = root; cur != null; cur = cur.next)
if (cur.left != null) {
cur.left.next = cur.right;
if (cur.next != null) cur.right.next = cur.next.left;
} else break;
return head;
}Time: O(N); Space: O(1)
117. Populating Next Right Pointers in Each Node II
类似的题目但是binary tree不是perfect。同样使用level order
Example 1:
My Solutions:
方法1: 和上题方法1类似，但注意一些区别。
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
Node rightNode = null;
// 这里要存下来这个size，因为后面我们会往queue里加入新的node，改变这个变量
int size = q.size();
// 每一层都是一个新的while loop循环
while (size > 0) { // 因为queue的长度会改变，所以使用while loop
Node cur = q.poll();
cur.next = rightNode;
rightNode = cur;
size--;
// 要先检查有没有左右节点，先加入右节点
if (cur.right != null) q.offer(cur.right);
if (cur.left != null) q.offer(cur.left);
}
}
return root;
}方法2:
public void connect(Node root) {
// levelHead is sentinel, keeps track of start node of next level
Node node = root, levelHead = new Node(0);
while (node != null) { // this loop is for different levels
// curr connects next fields in next level in current level
// first time in a level, it is same as leavelHead (with null next)
// but as soon as we get a non null child from node, it connects that child into its next
Node curr = levelHead;
while (node != null) {
if (node.left != null) {
// curr and levelHead points to the same object.
// This means after next line, same for levelHead.next = node.left
// This is how levelHead moves to next level
curr.next = node.left;
curr = curr.next; // move curr to next node
}
if (node.right != null) {
curr.next = node.right; // makes left connects to right
curr = curr.next; // move curr to next node
}
node = node.next; // move node to next in same level, end up null at rightmost
}
// current level ended in node being null
// take node from sentinel's next, which is next levels start
node = levelHead.next;
// make levelHead null
levelHead.next = null;
}
return root;
}Last updated