105. Construct Binary Tree from Inorder and Postorder Traversal

构建二叉树，是打一开始我接触 LeetCode 关于二叉树的题时就在想的问题了。

这个问题不太好想，但它的逆问题却非常成熟了，即如何遍历一颗二叉树？

稍微总结一下：

• 遍历二叉树
  • 深度优先遍历 --> (DFS) --> (stack)
    • 先序遍历 --> (先根遍历) --> (DFS) --> (stack, 寻左右压栈)
    • 中序遍历 --> (中根遍历) --> (DFS) --> (stack, 寻左根压栈, 取根再取右)
    • 后续遍历 --> (后根遍历) --> (DFS) --> (stack, 寻左根压栈, 取右再取根)
  • 广度优先遍历 --> (BFS) --> (queue)

首先是整体分类，按深度还是按广度？接着就是核心的算法思想：DFS 还是 BFS ？最后就是核心的数据结构，stack 还是 queue ?

我们从 tree 这种数据结构出发，经历了各种算法思想，最后又回到了本质的 stack or queue 这种数据结构上来。实际上是一种分治简化的策略，树作为一种中级数据结构来说，还是比较抽象的。

我们深度挖掘它，就会回到低一级的数据结构上去，如果再深度挖掘 stack or queue 呢？就会回到 LinkedList or array 上去。

所以数据结构既是算法的基础，却也是算法的抽象。我们学习数据结构时，不要将算法割裂开，它们是紧密联系相关的。

---

上面这段内容，纯粹是对 tree 基础知识的一个回顾与总结。我们说起 tree 总会先谈起如何遍历它。而这道题妙哉，反其道而行，让你组建它。

我们再次看看上面的分类图，可以很明显的发现，中序与后续，惊人的相似，连压栈规则都一致，仅仅是出栈规则有略微不同而已。这也是为什么 LeetCode 专门考察了 [08. Binary Tree Inorder Traversal](../08. Binary Tree Inorder Traversal) 和 [09. Binary Tree Preorder Traversal](../09. Binary Tree Preorder Traversal)，并没有再去专门考察 Postorder.

而正因为他们算法思想的相似，所以逆向生成二叉树的时候，最容易的方式，也是从它俩开始着手。

---

下面实例说明：

        1
      /  \
     2    3
    / \   /
   4   5 6
  /   /   \
 7   8     9

// inorder: 7,4,2,8,5,1,6,9,3
//              ^     ^     ^
// postorder: 7,4,8,5,2,9,6,3,1
//                    ^     ^ ^

可以看到的规律：

1. postorder.back() == 根节点的值
2. inorder中，根节点将左右子树分隔
3. 通过 inorder 中左右子树的 size ，可以在 postorder 中轻松找到 左右子树的根节点。

通过上述三条规律，可以很容易的总结出递归特性。

最终解法限于递归，思路比较清晰，但效率较低，可以改为迭代一试。