leetcode：105. 从前序与中序遍历序列构造二叉树

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1：
[中等] 105. 从前序与中序遍历序列构造二叉树 - 图1

  1. 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  2. 输出: [3,9,20,null,null,15,7]

示例 2：

  1. 输入: preorder = [-1], inorder = [-1]
  2. 输出: [-1]

解答 & 代码

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

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

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

  • 递归分别构建左、右子树

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. private:
    14.   // 哈希表，存储 inorder 数组的 <元素值，下标>
    15.   // 为了能在 O(1) 时间复杂度定位到 root 在 inorder 数组中的位置
    16.   unordered_map<int, int> valIdxMap;
    18.   // 递归构造二叉树
    19.   TreeNode* dfsBuildTree(vector<int>& preorder, int preLeft, int preRight, int inLeft, int inRight)
    20.   {
    21.       if(preLeft > preRight)
    22.           return nullptr;
    24.       // 前序位置：构造根节点
    25.       int rootVal = preorder[preLeft];
    26.       TreeNode* root = new TreeNode(rootVal);
    27.       int rootIdxOfInOrder = valIdxMap[rootVal];        // root 在 inorder 数组中的位置
    28.       int leftTreeLen = rootIdxOfInOrder - inLeft;    // 左子树长度
    29.       // 递归构造左、右子树
    30.       root->left = dfsBuildTree(preorder, preLeft + 1, preLeft + leftTreeLen, inLeft, rootIdxOfInOrder - 1);
    31.       root->right = dfsBuildTree(preorder, preLeft + leftTreeLen + 1, preRight, rootIdxOfInOrder + 1, inRight);
    32.       // 后序位置：返回根节点
    33.       return root;
    34.   }
    35. public:
    36.   TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    37.       // 将 inorder 数组存入哈希表
    38.       for(int i = 0; i < inorder.size(); ++i)
    39.           valIdxMap[inorder[i]] = i;
    40.       return dfsBuildTree(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    41.   }
    42. };

    复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：

  • 空间复杂度 O(N)：哈希表复杂度 O(N)

执行结果：

  1. 执行结果：通过
  3. 执行用时：16 ms, 在所有 C++ 提交中击败了 75.09% 的用户
  4. 内存消耗：25.7 MB, 在所有 C++ 提交中击败了 44.37% 的用户