Repository navigation
Expand file tree
/
Copy pathPopulatingNextRightPointersinEachNode.java
More file actions
69 lines (66 loc) · 3.11 KB
/
Copy pathPopulatingNextRightPointersinEachNode.java
File metadata and controls
69 lines (66 loc) · 3.11 KB
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
package com.bytecode.leetcode.tree;
import java.util.LinkedList;
import java.util.Queue;
/**
* 116. Populating Next Right Pointers in Each Node
* <p>
* 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:
* <p>
* 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.
* <p>
* Initially, all next pointers are set to NULL.
* <p>
* Example:
* <p>
* Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
* <p>
* Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
* <p>
* 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.
* <p>
* <a href="https://leetcode.com/problems/populating-next-right-pointers-in-each-node/">116. Populating Next Right Pointers in Each Node</a>
* <p>
* <a href="https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/">116. 填充每个节点的下一个右侧节点指针</a>
* <p>
* Created by vencial on 2019-09-10.
*/
public class PopulatingNextRightPointersinEachNode {
/**
* 1. 把结点放入到队列中
* 2. 结点出队, 并把结点的左子结点指向右子结点, 如果结点的next指针不为空, 则把结点的右子结点指向next的左子结点(基于是完美二叉树)
* <p>
* 1. push node to queue
* 2. poll from the queue, let the next of the left tree pointer to the right tree, and if next pointer is not null,
* then let the next of the right tree pointer to the left of the next pointer
*
* @param root root
* @return Node
*/
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.left != null) {
node.left.next = node.right;
if (node.next != null) {
node.right.next = node.next.left;
}
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}