【算法题】重建二叉树

这题说的是根据前序遍历数组和中序遍历数组来重建二叉树。我们知道前序遍历数组的第一个元素一定是根节点，在中序遍历数组中，根节点前面的都是根节点左子树上的节点，根节点后面的都是根节点右子树上的节点。左右两棵子树我们可以使用递归的方式继续创建。

我们首先使用前序数组的第一个元素创建根节点，然后查询该节点在中序遍历数组中的位置，把中序数组分成两部分，一部分是根节点左子树的节点，一部分是根节点右子树的节点。为了方便查询，我们可以提前把中序数组存储到 map 中。

比如前序数组是：{1,2,4,7,3,5,6,8}，中序数组是：{4,7,2,1,5,3,8,6}

那么 1 就是根节点，中序数组中 1 左边的 {4,7,2} 就是根节点左子树上的所有节点， 1 的右边 {5,3,8,6} 就是根节点右子树上的所有节点，如下图所示。

    public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
        // 为了方便后续进行查找，先把中序数组的所有值存储到map中
        Map<Integer, Integer> mp = new HashMap<>();
        int n = vinOrder.length;
        for (int i = 0; i < n; i++)
            mp.put(vinOrder[i], i);
        return build(preOrder, mp, 0, 0, n - 1);
    }

    /**
     * @param preorder 前序遍历的数组
     * @param mp       map，存储的是中序遍历的数组
     * @param preStart 前序遍历数组中的第一个元素下标
     * @param inStart  中序遍历数组的起始位置
     * @param inEnd    中序遍历数组的结束位置
     * @return
     */
    private TreeNode build(int[] preorder, Map<Integer, Integer> mp,
                           int preStart, int inStart, int inEnd) {
        if (inStart > inEnd)// 表示数组被访问完了。
            return null;
        // 使用前序数组的第一个元素创建node节点
        TreeNode node = new TreeNode(preorder[preStart]);
        // 查找node节点在中序数组中位置
        int index = mp.get(node.val);
        int leftCnt = index - inStart;// node节点左子树的所有节点个数。
        // 前序数组区间划分：
        // [preStart, preStart]根节点
        // [preStart + 1, preStart + leftCount]左子树
        // [preStart + leftCount + 1, ……]右子树
        // 中序数组区间划分：
        // [inStart, index - 1]左子树
        // [index, index]根节点
        // [index + 1, inEnd]右子树
        node.left = build(preorder, mp, preStart + 1, inStart, index - 1);// 递归创建左子树和右子树
        node.right = build(preorder, mp, preStart + leftCnt + 1, index + 1, inEnd);
        return node;
    }

public:
    TreeNode *reConstructBinaryTree(vector<int> &preOrder, vector<int> &vinOrder) {
        // 为了方便后续进行查找，先把中序数组的所有值存储到map中
        unordered_map<int, int> mp;
        int n = vinOrder.size();
        for (int i = 0; i < n; i++)
            mp[vinOrder[i]] = i;
        return build(preOrder, mp, 0, 0, n - 1);
    }

    /**
     * @param preorder 前序遍历的数组
     * @param mp       map，存储的是中序遍历的数组
     * @param preStart 前序遍历数组中的第一个元素下标
     * @param inStart  中序遍历数组的起始位置
     * @param inEnd    中序遍历数组的结束位置
     * @return
     */
    TreeNode *build(vector<int> &preorder, unordered_map<int, int> &mp,
                    int preStart, int inStart, int inEnd) {
        if (inStart > inEnd)// 表示数组被访问完了。
            return nullptr;
        // 使用前序数组的第一个元素创建node节点
        auto *node = new TreeNode(preorder[preStart]);
        // 查找node节点在中序数组中位置
        int index = mp[node->val];
        int leftCnt = index - inStart;// node节点左子树的所有节点个数。
        // 前序数组区间划分：
        // [preStart, preStart]根节点
        // [preStart + 1, preStart + leftCount]左子树
        // [preStart + leftCount + 1, ……]右子树
        // 中序数组区间划分：
        // [inStart, index - 1]左子树
        // [index, index]根节点
        // [index + 1, inEnd]右子树
        node->left = build(preorder, mp, preStart + 1, inStart, index - 1);// 递归创建左子树和右子树
        node->right = build(preorder, mp, preStart + leftCnt + 1, index + 1, inEnd);
        return node;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》