Post-order traversal of a binary tree
Post-order traversal of a tree is a recursive procedure, where you first the left subtree of a node, then visit its right subtree, and then the node itself:
Visit the left subtree (
node.left)Visit the right subtree (
node.right)Visit the current node
Given a binary tree, you are asked to perform a post-order traversal on it.
Input
The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given by traversing from the left to the right subtree every time. A value of 0 means that the node does not exist. It’s guaranteed that the input binary tree is valid.
Output
The program should print the values in the nodes of a binary tree when performing a post-order traversal. All the values should be separated by a space.
Examples
Input | Output |
|---|---|
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 9 4 5 2 6 7 3 1 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 5 2 6 7 3 1 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 5 2 6 8 9 7 3 1 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 7 8 5 2 6 3 1 |
Explanation
Example 1:
Example 2:
Example 3:
Example 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB