从前序与中序遍历序列构造二叉树

核心顿悟突破口

前序遍历的第一个元素就是根节点；根节点在中序遍历中的位置可以把序列划分成左右子树。使用哈希表保存 inorder 中每个值的下标，并通过前序区间与中序区间递归构建，可以把每次查找根位置从 O(N) 优化为 O(1)，整体达到 O(N)。