Connect Level Order Siblings (medium)
Problem Statement
Given a binary tree, connect each node with its level order successor. The last node of each level should point to a null
node.
Example 1:
Example 2:
Try it yourself
Try solving this question here:
import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode next;TreeNode(int x) {val = x;left = right = next = null;}// level order traversal using 'next' pointervoid printLevelOrder() {TreeNode nextLevelRoot = this;while (nextLevelRoot != null) {TreeNode current = nextLevelRoot;nextLevelRoot = null;while (current != null) {System.out.print(current.val + " ");if (nextLevelRoot == null) {if (current.left != null)nextLevelRoot = current.left;else if (current.right != null)nextLevelRoot = current.right;}current = current.next;}System.out.println();}}};class ConnectLevelOrderSiblings {public static void connect(TreeNode root) {// TODO: Write your code here}public static void main(String[] args) {TreeNode root = new TreeNode(12);root.left = new TreeNode(7);root.right = new TreeNode(1);root.left.left = new TreeNode(9);root.right.left = new TreeNode(10);root.right.right = new TreeNode(5);ConnectLevelOrderSiblings.connect(root);System.out.println("Level order traversal using 'next' pointer: ");root.printLevelOrder();}}
Solution
This problem follows the Binary Tree Level Order Traversal pattern. We can follow the same BFS approach. The only difference is that while traversing a level we will remember the previous node to connect it with the current node. ...