[LeetCode]Construct Binary Tree from Preorder and Postorder Traversal

这道题和Construct Binary Tree from Preorder and Inorder Traversal是类似的，同样我们也有recursive和iterative两种解法。

因为preorder是遵从[root][left-subtree][right-subtree]的格式，而postorder的格式是[left-subtree][right-subtree][root]，所以我们可以通过这些信息把前后序两个序列划分成左右子树和根，然后递归地进行树的构造。划分左右子树需要O(n)的时间，时间复杂度分析T(N) = 2 * T(n / 2) + n，T = O(n * log n)，代码如下：

iterative的做法我们还是用stack, 关键点在于postorder序列能给我们提供什么信息，我们可以知道当我们扫到后序序列的某一个节点时，其要么是叶节点，要么左右子树都已经遍历完了。对于栈上的元素而言，要么我们取前序的下一个元素当左子节点；要么当其再次出现在栈顶时，说明左子树都被扫过了，我们把前序的下一个当做右子结点并压入栈；当我们第三次看见塔出现在栈顶的时候，说明左右子树都遍历完了，这个时候栈顶元素一定是等于后序序列的当前元素的，我们pop出栈即可。时间空间复杂度均为O(n)，代码如下：