leetcode 链接：从前序与中序遍历序列构造二叉树

题目

根据一棵树的前序遍历与中序遍历构造二叉树。


注意: 你可以假设树中没有重复的元素。

示例：

  1. 前序遍历 preorder = [3,9,20,15,7]
  2. 中序遍历 inorder = [9,3,15,20,7]
  3. 返回如下的二叉树：
  4.     3
  5.    / \
  6.   9  20
  7.     /  \
  8.    15   7

解答 & 代码

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

image.png
因此，算法流程如下：

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

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

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

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

        // 用前序遍历数组左边界的值来构建 root 节点
        int rootVal = preorder[preLeft];
        TreeNode* root = new TreeNode(rootVal);

        // 通过哈希表定位 root 节点的值在中序遍历数组中的下标
        int inRootIdx = inOrderMap[rootVal];
        // root 节点的左子树的节点数
        int leftNodeNum = inRootIdx - inLeft;

        // 递归得到左、右子树
        root->left = recurBulidTree(preorder, preLeft + 1, preLeft + leftNodeNum, 
            inLeft, inRootIdx - 1);
        root->right = recurBulidTree(preorder, preLeft + leftNodeNum + 1, preRight,
            inRootIdx + 1, inRight);

        // 返回根节点
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int nodeNum = preorder.size();
        for(int i = 0; i < nodeNum; ++i)
            inOrderMap[inorder[i]] = i;
        return recurBulidTree(preorder, 0, nodeNum - 1, 0, nodeNum - 1);
    }
};

执行结果：

执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了 20.87% 的用户
内存消耗：121.4 MB, 在所有 C++ 提交中击败了 6.73% 的用户