Just as the title, you will be given a pre-order traversal of BST, please print the post-order traversal of it.
(BST is a tree that the number of each node will be larger than its left subtree, and smaller than its right subtree.)
Think 1: Is binary search useful in this problem?
Think 2: Is it possible not to build the tree?
hint1: just by looking at the sequence, can you find which are in the left subtree, which are in the right subtree?
hint2: the left subtree and the right subtree are both a tree, don't you think it sounds familiar? (recur...)
hint3: is there any way that we can find the beginning of the right subtree quickly?
The first line contains one integer N, means there are n node in this tree.
The next line has N different integers, which is the pre-order traversal of the BST. Each number is between [1, 1e9].
For testcase 1~3: 1 <= N <= 1e4.
For testcase 4~6: 1 <= N <= 2e5.
Print the post-order of the BST.
Notice: print a space after each number and DO NOT print '\n' at last.