700248. Level Order Line by Line
Here is a detailed Markdown blog post for the Level Order Line by Line problem:
Level Order Traversal Line by Line
Summary
The Level Order Traversal Line by Line problem involves traversing a binary tree in level order, but instead of printing all nodes at each level, we want to print them line by line. This means that all nodes at the first level are printed on the same line, followed by all nodes at the second level on the next line, and so on.
Detailed Explanation
To solve this problem, we can use a queue-based approach to traverse the binary tree in level order. We will start by adding the root node to the queue. Then, we will enter a loop that continues until the queue is empty.
Inside the loop, we will first dequeue all nodes at the current level and print them on the same line. To do this, we can use a StringBuilder or a string concatenation approach to build the line of output. Once we have printed all nodes at the current level, we will enqueue the next level's nodes.
Here is a step-by-step breakdown of the solution:
- Initialize an empty queue.
- Add the root node to the queue.
- Loop until the queue is empty:
- Dequeue all nodes at the current level and print them on the same line.
- Enqueue the next level's nodes.
- Print a newline character after printing each level.
Here is an ASCII art diagram of the binary tree for better understanding:
1
/
2 3
/ \
4 5 6
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(m), where m is the maximum level of the tree.
Optimized Solutions
Java
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void printLevelOrderLineByLine(Node root) {
if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
Node node = queue.poll();
System.out.print(node.val + " ");
}
System.out.println();
}
}
public static class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
}