117. Populating Next Right Pointers in Each Node II 发表于 2021-11-20 BFS12345678910111213141516171819202122232425262728class Solution { public Node connect(Node root) { if (root == null) { return null; } Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { Node pre = null; for (int i = queue.size(); i > 0; i--) { Node node = queue.poll(); node.next = pre; pre = node; if (node.right != null) { queue.add(node.right); } if (node.left != null) { queue.add(node.left); } } } return root; }} Iterate12345678910111213141516171819202122232425262728293031class Solution { public Node connect(Node root) { if (root == null) { return null; } Node leftmost = root; while (leftmost != null) { Node dummyHead = new Node(); Node pre = dummyHead; Node node = leftmost; while (node != null) { if (node.left != null) { pre.next = node.left; pre = pre.next; } if (node.right != null) { pre.next = node.right; pre = pre.next; } node = node.next; } leftmost = dummyHead.next; } return root; }} Reference117. Populating Next Right Pointers in Each Node II