leetcode 链接：剑指 Offer 07. 重建二叉树
相同题目：
[中等] 105. 从前序与中序遍历序列构造二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]
Output: [-1]

解答 & 代码

• 前序遍历数组的结构为 [根节点, [左子树节点], [右子树节点]]
• 中序遍历数组的结构为 [[左子树节点], 根节点, [右子树节点]]

因此，算法流程如下：

• 通过前序遍历数组左边界的值来构建根节点 root
• 查找根节点的值在中序遍历数组中的位置 rootIdxOfInorder ，就可以将中序遍历数组划分为左子树区间和右子树区间
  • 可以事先用哈希表存储中序遍历数组中的 <节点值, 下标> 键值对，在 O(1) 的时间复杂度内快速定位 rootIdxOfInorder
  • 注意哈希表需要作为类成员，如果作为递归函数的参数，提交会超时
• 根据 rootIdxOfInorder -中序遍历数组左边界下标 inLeft，就可以得到左子树节点数目 leftSize，就能将前序遍历数组划分为左子树区间和右子树区间
• 递归分别构建左、右子树

时间复杂度 O(N)，空间复杂度 O(N)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    // 哈希表，存储中序遍历的<数值, 下标>键值对，
    // 使得可以用节点的值快速查找其在中序遍历数组中的下标
    unordered_map<int, int> inorderMap;

    // 递归构造二叉树
    // preorder: 前序遍历数组，preLeft: 前序遍历数组的左边界（含），preRight: 前序遍历数组的右边界（含）
    // inLeft: 中序遍历的左边界（含），inRight: 中序遍历的右边界（含）
    TreeNode* rebuildTree(vector<int> preorder, int preLeft, int preRight, int inLeft, int inRight)
    {
        // 递归结束条件：左边界大于右边界，返回空
        if(preLeft > preRight || inLeft > inRight)
            return nullptr;

        // 用前序遍历数组左边界的值来构建 root 节点
        TreeNode* root = new TreeNode(preorder[preLeft]);
        // 通过哈希表定位 root 节点的值在中序遍历数组中的下标
        int rootIdxOfInorder = inorderMap[root->val];
        // 计算 root 节点的左子树的节点数
        int leftSize = rootIdxOfInorder - inLeft;
        // 递归得到左、右子树
        root->left = rebuildTree(preorder, preLeft + 1, preLeft + leftSize, inLeft, rootIdxOfInorder - 1);
        root->right = rebuildTree(preorder, preLeft + leftSize + 1, preRight, rootIdxOfInorder + 1, inRight);
        // 返回 root 节点
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); ++i)
            inorderMap[inorder[i]] = i;
        return rebuildTree(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

执行结果：

执行结果：通过

执行用时：44 ms, 在所有 C++ 提交中击败了 26.30% 的用户
内存消耗：120.8 MB, 在所有 C++ 提交中击败了 6.48% 的用户