328. Postorder Traversal
Print the values in postorder: everything in the left subtree, then everything in the right subtree, then the node itself.
4
/ \
2 6 postorder is 1 3 2 5 7 6 4
/ \ / \
1 3 5 7
Postorder visits a node only after BOTH its children are finished, which is what makes it the order for deleting a tree or computing anything that depends on the children's answers. Every solution in problems 321 to 325 was a postorder in disguise.
The neat iterative trick is worth knowing: run a preorder that visits right before left, then reverse the result.
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 postorder, separated by single spaces.