从前序与中序遍历序列构造二叉树

题面

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

示例 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]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

分析

• 前序遍历中，第一个元素一定是根节点，在中序遍历中找到该节点的位置，那么该节点左边就是左子树，右边就是右子树，循环这个过程即可

• 代码实现

  /**
   * 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 {
  public:
      TreeNode* buildSubTree(vector<int>& preorder, vector<int>& inorder,
                             vector<int> indexes) {
          int preorderl = indexes[0], preorderr = indexes[1],
              inorderl = indexes[2], inorderr = indexes[3];
          if (inorderl > inorderr || preorderl > preorderr)
              return nullptr;
          int root = preorder[preorderl];
          int i = inorderl;
          for (; i <= inorderr; i++) {
              if (inorder[i] == root)
                  break;
          }
          int leftLength = i - inorderl, rightLength = inorderr - i;
          TreeNode* left = buildSubTree(
              preorder, inorder,
              {preorderl + 1, preorderl + leftLength, inorderl, i - 1});
          TreeNode* right = buildSubTree(preorder, inorder,
                                         {preorderl + leftLength + 1,
                                          preorderl + leftLength + rightLength,
                                          i + 1, inorderr});
          TreeNode* cur = new TreeNode(root);
          cur->left = left;
          cur->right = right;
          return cur;
      }
      TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
          return buildSubTree(preorder, inorder,
                              {0, static_cast<int>(preorder.size() - 1), 0,
                               static_cast<int>(inorder.size() - 1)});
      }
  };

• 逻辑优化

  /**
   * 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> valToIndex;
      
      // 简化的递归构建函数，使用独立参数传递区间，语义更清晰
      TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                     vector<int>& inorder, int inStart, int inEnd) {
          // 递归终止条件：区间无效
          if (preStart > preEnd || inStart > inEnd) return nullptr;
          
          // 前序遍历第一个元素就是根节点
          int rootVal = preorder[preStart];
          TreeNode* root = new TreeNode(rootVal);
          
          // 快速找到根节点在中序遍历中的位置（O(1)）
          int rootIdx = valToIndex[rootVal];
          // 左子树的节点数量
          int leftSize = rootIdx - inStart;
          
          // 递归构建左右子树
          // 左子树：前序[preStart+1, preStart+leftSize]，中序[inStart, rootIdx-1]
          root->left = build(preorder, preStart + 1, preStart + leftSize,
                            inorder, inStart, rootIdx - 1);
          // 右子树：前序[preStart+leftSize+1, preEnd]，中序[rootIdx+1, inEnd]
          root->right = build(preorder, preStart + leftSize + 1, preEnd,
                             inorder, rootIdx + 1, inEnd);
          
          return root;
      }
      
  public:
      TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
          // 初始化哈希表，缓存中序遍历值的索引
          for (int i = 0; i < inorder.size(); ++i) {
              valToIndex[inorder[i]] = i;
          }
          // 调用递归函数，传递完整区间
          return build(preorder, 0, preorder.size() - 1,
                      inorder, 0, inorder.size() - 1);
      }
  };