329. Level Order Traversal
Print the values row by row from the top: the root, then everything one step below it, then everything two steps below, and so on. Within a row, print left to right.
4
/ \
2 6 level order is 4 2 6 1 3 5 7
/ \ / \
1 3 5 7
This is the one traversal that is NOT naturally recursive. The other three follow a branch to its end before backing up; this one has to finish an entire row before starting the next, and a recursion has no way to hold that.
A queue does. Take a node from the front, print it, and add its children to the back. Nodes then come out in exactly the order they were discovered, which is row by row.
The only change from the stack versions is which end you remove from, and that single change turns depth-first into breadth-first.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print the values in level order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.