336. Left View of a Tree
Print the first node of each row, top to bottom. That is what you would see standing to the left of the tree and looking across it.
4
/ \
2 6 left view is 4 2 1
/ \ / \
1 3 5 7
Note that the left view is NOT the leftmost path. If the leftmost branch is short, a node from a different branch becomes the first thing visible on the rows below it, which is what the uneven test checks.
A level-order walk gives it directly: the first node reached at each new depth is the answer for that depth.
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 first value of each row, top to bottom, separated by single spaces.