Construct Binary Tree from Preorder and Inorder Traversal

一道比较复杂的二叉树类题目，先给出题目：

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

给出了先序遍历和中序遍历的结果，要构造出对应的二叉树。我们应该对先序遍历和中序遍历很熟悉了，先序遍历遵循根左右的遍历顺序，中序遍历遵循左根右的遍历顺序。

对于先序遍历来说，任意一个顺序，第一个元素总是某个子树的根节点，而右侧的所有元素分别是左子树的遍历结果和右子树的遍历结果 (根, (左子树), (右子树))。比如我们有以下遍历结果：

1,2,3,4,5

则1肯定为根节点，2,3,4,5分别是左子树和右子树的遍历结果，当然是连续的，但是仅仅从这个信息，我们无法分别哪些是左子树的遍历结果，哪些是右子树的遍历结果，我们需要额外的信息。

对于中序遍历来说，遍历的数据分别是((左子树), 根， (右子树))，所以对于先序遍历我们无法获得的分割点，从这里可以获得。

于是我们按着这个思路，首先根据先序遍历的第一个元素来确定根节点，然后从中序遍历的结果中获取左子树和右子树的范围，然后找出对应的先序遍历的范围，把左右子树的范围找出来，比如把1,2,3,4,5分割为1,(2,3),(4,5)，我们就知道23是左子树的遍历结果，45是右子树的遍历结果。有了这个信息之后，我们可以再次对45做上述的步骤，把4当做根节点，找出对应的左子树和右子树范围，这是一个遍历的过程。

以题目的例子为例，我们有preorder [3,9,20,15,7] 与 inorder [9,3,15,20,7]，那么我们依次进行一下操作：

1. 3为根节点，从inorder中找出3的位置，于是inorder分割为 [(9),3,(15,20,7)]，从而得知9为左子树的遍历结果，15,20,7为右子树的遍历结果，根据这个信息，我们可以把preorder进行分割 [3,(9),(20,15,7)]，获得了根节点为3，于是我们得到了左子树的先序9和后序9,右子树的先序20,15,7和后序15,20,7。
2. 继续对9和15,7做1的操作，9为3的左子树的根节点，20为3的右子树的根节点。对于9来说，已经没有左子树和右子树了。而对于先序20,15,7来说，从中序找到根节点20，于是可知15是左子树，7是右子树，则此操作完成。

下面是大致的代码：

class ConstructBinaryTreeFromPreorderAndInorderTraversal : public TreeNodeCls {
public:
    static void test() {
        int prevals[] = {3, 9, 20, 15, 7};
        vector<int> preorder(prevals, prevals + sizeof(prevals) / sizeof(prevals[0]));
        int invals[] = {9, 3, 15, 20, 7};
        vector<int> inorder(invals, invals + sizeof(invals) / sizeof(invals[0]));
        auto ret = buildTree(preorder, inorder);
    }

    static TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || preorder.size() != inorder.size()) {
            return nullptr;
        }
        // Generate quick search map
        unordered_map<int, int> psm;
        for (int i = 0; i < preorder.size(); i++) {
            psm[preorder[i]] = i;
        }
        unordered_map<int, int> ism;
        for (int i = 0; i < inorder.size(); i++) {
            ism[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, nullptr, false, psm, ism);
    }

    static TreeNode* build(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie, TreeNode *parent, bool left, unordered_map<int, int> &psm, unordered_map<int, int> &ism) {
        if (ps > pe) {return nullptr;}
        TreeNode *apnode = parent;
        if (0 == ps) {
            apnode = new TreeNode(preorder[0]);
        } else {
            if (left) {
                apnode->left = new TreeNode(preorder[ps]);
                apnode = apnode->left;
            } else {
                apnode->right = new TreeNode(preorder[ps]);
                apnode = apnode->right;
            }
        }
        if (ps == pe) {
            // Last node appended
            return apnode;
        }
        // Find root node in inorder
        int index = ism[preorder[ps]];
        // Find left and right range in preorder
        if (is < index) {
            int spi = -1;
            for (int i = is; i < index; i++) {
                int ii = psm[inorder[i]];
                spi = std::max(spi, ii);
            }
            if (spi >= 0) {
                build(preorder, ps + 1, spi, inorder, is, index - 1, apnode, true, psm, ism);
            }
        }
        if (ie > index) {
            int spi = preorder.size();
            for (int i = ie; i > index; i--) {
                int ii = psm[inorder[i]];
                spi = std::min(spi, ii);
            }
            if (spi < preorder.size()) {
                build(preorder, spi, pe, inorder, index - 1, ie, apnode, false, psm, ism);
            }
        }

        return apnode;
    }
};