题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。To do it!

示例1：
输入： preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出： [3,9,20,null,null,15,7]
示例2：
输入： preorder = [-1], inorder = [-1]
输出： [-1]
限制： 0 <= 节点个数 <= 5000

题解

前序遍历的顺序为：先遍历根节点；随后递归地遍历左子树；最后递归地遍历右子树。
二叉树中序遍历的顺序为：先递归地遍历左子树；随后遍历根节点；最后递归地遍历右子树。
算法详解

分治递归

对于任意一棵树，

前序遍历的形式：[根节点, [左子树的前序遍历结果], [右子树的前序遍历结果]]；
中序遍历的形式：[[左子树的中序遍历结果], 根节点, [右子树的中序遍历结果]]。

前序遍历的第一个节点就是根节点，只要在中序遍历中定位到根节点，就可以知道左右子树的节点数目。这样就知道了左右子树的前序遍历和中序遍历结果，得到与原问题相同的两个子问题，如此递归构造出左右子树，再接到根节点的左右位置。

在中序遍历中对根节点进行定位时，一种简单的方法是直接遍历整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高，题解中使用哈希表来辅助定位，对中序遍历结果的节点值和索引建立映射，在构造二叉树之前，先对中序遍历的结果进行遍历，构造出哈希表，在此后构造二叉树的过程中，只需 O(1) 的时间即可定位到根节点。

class Solution {
    // 建立中序遍历 inorder 的哈希表，从值映射到下标
    // 使每次在中序遍历中寻找根节点下标时 root_idx_inorder 能够 O(1)
    unordered_map<int, int> inorderHash;
    // 根据前序遍历区间和中序遍历区间重建二叉树，返回根节点
    TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder, 
    int pre_left, int pre_right, int in_left, int in_right) {
        // 没有节点了，返回空指针
        if (pre_left > pre_right) return nullptr;
        // 先序遍历的第一个节点为根节点
        TreeNode* root = new TreeNode(preorder[pre_left]);
        // 根节点在中序遍历中的下标
        int root_idx_inorder = inorderHash[root->val];
        // 在中序遍历中，可以根据根节点下标求出左子树的节点数，后序递归用
        int left_subtree_size = root_idx_inorder - in_left;
        // 根节点的左子树，找到左子树对应的前序遍历区间和中序遍历区间
        root->left = buildTree(preorder, inorder, 
        pre_left + 1, pre_left + left_subtree_size, in_left, root_idx_inorder - 1);
        // 根节点的右子树，找到右子树对应的前序遍历区间和中序遍历区间
        root->right = buildTree(preorder, inorder,
        pre_left + left_subtree_size + 1, pre_right, root_idx_inorder + 1, in_right);
        // 返回根节点
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();     // 节点数
        for (int i = 0; i < n; ++i) inorderHash[inorder[i]] = i;
        return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

时间复杂度：O(n)，空间复杂度：O(n)
其中 n 是树中的节点个数。除去返回答案需要的 O(n) 空间之外，需要使用 O(n) 的空间存储哈希映射，以及 O(h) (其中 h 是树的高度) 空间表示递归时的栈空间。这里 h <= n，所以总空间复杂度为 O(n)。

迭代法

迭代法的本质是：若这棵树只有左子树，相当于一条单链表，那前序遍历和中序遍历的结果是相反的顺序。利用栈来逆序存放前序遍历的结果，一旦遍历到最左下方，就开始弹出栈，同时开始扫描中序遍历的结果。
若过程中栈顶弹出的节点值和中序遍历从左到右遍历的节点值不相等，则说明至此不是单链表结构，而是多了个右孩子插在最后一个弹出节点的右边。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if (n == 0) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> st;
        st.push(root);
        int inorderIdx = 0;
        for (int i = 1; i < n; ++i) {
            TreeNode* node = st.top();
            // 这里入栈的都是某个根节点的左孩子，在下次遍历，左孩子又作为根节点参与遍历
            // 如此一直压栈，直到当前根节点的最左下方
            if (node->val != inorder[inorderIdx]) {     // preorder[i] 还是左孩子，入栈
                node->left = new TreeNode(preorder[i]);
                st.push(node->left);
            } else {    // preorder[i] 是右孩子，循环出栈找到 preorder[i] 的父节点，即最后出栈的
                while (!st.empty() && st.top()->val == inorder[inorderIdx]) {   // 过滤叶子节点
                    node = st.top();        // 循环停止后，最后出栈的节点为 preorder[i] 的父节点
                    st.pop();               // preorder[i] 为父节点的右孩子节点  
                    ++inorderIdx;
                }
                node->right = new TreeNode(preorder[i]);
                st.push(node->right);       // 右孩子节点也入栈，作为根节点参与后面的遍历
            }
        }
        return root;
    }
};