构建二叉树，是打一开始我接触 LeetCode 关于二叉树的题时就在想的问题了。
这个问题不太好想，但它的逆问题却非常成熟了，即如何遍历一颗二叉树？
稍微总结一下：
首先是整体分类，按深度还是按广度？接着就是核心的算法思想：DFS 还是 BFS ？最后就是核心的数据结构，stack 还是 queue ?
我们从 tree 这种数据结构出发，经历了各种算法思想，最后又回到了本质的 stack or queue 这种数据结构上来。实际上是一种分治简化的策略，树作为一种中级数据结构来说，还是比较抽象的。
我们深度挖掘它，就会回到低一级的数据结构上去，如果再深度挖掘 stack or queue 呢？就会回到 LinkedList or array 上去。
所以数据结构既是算法的基础，却也是算法的抽象。我们学习数据结构时，不要将算法割裂开，它们是紧密联系相关的。
上面这段内容，纯粹是对 tree 基础知识的一个回顾与总结。我们说起 tree 总会先谈起如何遍历它。而这道题妙哉，反其道而行，让你组建它。
我们再次看看上面的分类图，可以很明显的发现，中序与后续，惊人的相似，连压栈规则都一致，仅仅是出栈规则有略微不同而已。这也是为什么 LeetCode 专门考察了 08. Binary Tree Inorder 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
// ^ ^ ^可以看到的规律：
通过上述三条规律，可以很容易的总结出递归特性。
最终解法限于递归，思路比较清晰，但效率较低，可以改为迭代一试。
#include <cstddef>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
using vcIt = vector<int>::const_iterator;
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
return buildTree(inorder.cbegin(), inorder.cend(), postorder.cbegin(), postorder.cend());
}
TreeNode *buildTree(vcIt inBeg, vcIt inEnd, vcIt postBeg, vcIt postEnd) {
if (inBeg >= inEnd || postBeg >= postEnd) return NULL;
TreeNode *root = new TreeNode(*prev(postEnd));
auto inRoot = find(inBeg, inEnd, root->val);
root->left = buildTree(inBeg, inRoot, postBeg, next(postBeg, inRoot-inBeg));
root->right = buildTree(next(inRoot), inEnd, next(postBeg, inRoot-inBeg), prev(postEnd));
return root;
}
};