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

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

class Solution {
  TreeNode *Tree;

public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty())
        return {};

    int Size = preorder.size();
    int RootVal = preorder.front();
    int RootIdx = 0;
    for (RootIdx = 0; RootIdx < Size; ++RootIdx)
      if (RootVal == inorder[RootIdx])
        break;

    vector<int> LPre(preorder.begin() + 1,
                     preorder.begin() + 1 + RootIdx);
    vector<int> RPre(preorder.begin() + 1 + RootIdx,
                     preorder.end());
    vector<int> LIn(inorder.begin(),
                    inorder.begin() + RootIdx);
    vector<int> RIn(inorder.begin() + 1 + RootIdx,
                    inorder.end());
    TreeNode *L = buildTree(LPre, LIn);
    TreeNode *R = buildTree(RPre, RIn);
    return new TreeNode(RootVal, L, R);
  }
};

这题的关键就在于要理解前序和中序遍历序列的递归特质，即对于任意一颗树而言，前、中序遍历的形式分别是：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

二刷

有一点必须要注意：如果采用每次都构造新的子数组的方法，那么你就只能采用线性查找，而不能用 unordered_map 辅助查找，因为一开始记录在 unordered_map 当中的 RootIdx 值，大概率是会越界的！

所以对于这种问题，最好的方法仍然是采用全局数组和手动指定下标的方式——其实跟分治和二分一样。这样做的好处，一是避免了不必要的创建对象开销，二是能够保留绝对位置的读取能力。

class Solution {
  std::unordered_map<int, int> InOrderIdx;

  TreeNode* Build(vector<int>& Pre, vector<int>& In, int PL, int PR, int IL, int IR) {
    if (PL == PR)
      return {};

    int Root = Pre[PL];
    int RootIdx = InOrderIdx[Root];
    int LeftSize = RootIdx - IL;

    TreeNode *L = Build(Pre, In, PL + 1, PL + 1 + LeftSize, IL, IL + LeftSize);
    TreeNode *R = Build(Pre, In, PL + 1 + LeftSize, PR, IL + LeftSize + 1, IR);
    return new TreeNode(Root, L, R);
  }

public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int Size = inorder.size();
    for (int i = 0; i < Size; ++i)
      InOrderIdx[inorder[i]] = i;
    return Build(preorder, inorder, 0, Size, 0, Size);
  }
};

这时就需要注意，PL 和 IL 之类的变量全部都变成了绝对位置，所以计算的时候也应该按照绝对位置的思路去求偏移、求差值，这是与相对位置的思路不一样的地方。

三刷 

class Solution {
  std::unordered_map<int, int> InIdxMap;
  TreeNode *Build(vector<int> &Pre, vector<int> &In, int PreL, int PreR, int InL, int InR) {
    if (PreL == PreR)
      return {};

    // XXX By default you should consider all indices here ABSOLUTE!!!
    // int Val = Pre.front();
    int Val = Pre[PreL];
    int InIdx = InIdxMap[Val];
    int LSize = InIdx - InL;
    TreeNode *Root = new TreeNode(Val);
    Root->left = Build(Pre, In, PreL + 1, PreL + 1 + LSize, InL, InIdx);
    Root->right = Build(Pre, In, PreL + 1 + LSize, PreR, InIdx + 1, InR);
    return Root;
  }
public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); ++i)
      InIdxMap[inorder[i]] = i;
    return Build(preorder, inorder, 0, preorder.size(), 0, inorder.size());
  }
};

递归方法本身没什么好说的，但是，千万要注意绝对下标和相对下标的思维转换！！！

这个迭代方法说实话，有空估计还得再写一次。不太好写的。


class Solution {
public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty())
      return {};

    // Fire a Root first, since we need to create a tree FROM SCRATCH.
    TreeNode *Root = new TreeNode(preorder.front());
    std::stack<TreeNode *> Stack;
    Stack.push(Root);
    // The first value in each inorder SUBsequence must be the first node that
    // has NO LEFT CHILD.
    int CurrInIdx = 0;
    // Mind that this i here is ABSOLUTE index. Thus, we don't need to care if
    // we need to update it after rewinding the stack.
    for (int i = 1; i < preorder.size(); ++i) {
      int Val = preorder[i];
      TreeNode *Node = Stack.top();
      if (Node->val != inorder[CurrInIdx]) {
        // Keep finding until the leftmost tree in which we'll encounter the
        // first value in each SUBsequence.
        Node->left = new TreeNode(Val);
        Stack.push(Node->left);
      } else {
        // Whenever we enter this branch, we know that we've arrived at the root
        // of a SUBtree, which means that we've already visited all of its left
        // children (nullptr included). So it's time to rewind our stack, and go
        // to the right if it's high time - when val != inorder[CurrInIdx].
        while (!Stack.empty() && Stack.top()->val == inorder[CurrInIdx]) {
          Node = Stack.top();
          Stack.pop();
          ++CurrInIdx;
        }
        // Keep in mind that we're not simply traversing. We're CREATING.
        Node->right = new TreeNode(Val);
        Stack.push(Node->right);
      }
    }

    return Root;
  }
};

它的主要原理图示差不多可以这么理解： Pasted image 20260306141423.png 注意这个根据子树中序序列第一位无左孩子的原理而形成的「遇根退栈，前中倒序」的思路。其实还是挺优雅的，但就是代码不好记。

外层的 for (int i = 1; i < preorder.size(); ++i) {} 需要注意一下，这里其实隐含了绝对下标的思想。栈被退了？无所谓，访问的绝对位置继续向前就行。体现在上图就是，你可以看得出来，无论是前序还是中序数组，箭头的起始点一直是在严格右移的。

四刷 

class Solution {
  TreeNode *Build(vector<int> &Pr, vector<int> &In, int PrL, int PrR, int InL, int InR) {
    if (PrL == PrR)
      return nullptr;
    if (PrL == PrR - 1)
      return new TreeNode(Pr[PrL]);

    int Pivot = Pr[PrL];
    int InM;
    for (InM = InL; InM < InR; ++InM) {
      if (In[InM] == Pivot)
        break;
    }
    int LeftLen = InM - InL;
    TreeNode *New = new TreeNode(Pivot);
    New->left = Build(Pr, In, PrL + 1, PrL + 1 + LeftLen, InL, InM);
    New->right = Build(Pr, In, PrL + 1 + LeftLen, PrR, InM + 1, InR);
    return New;
  }
public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return Build(preorder, inorder, 0, preorder.size(), 0, inorder.size());
  }
};

这个解法中间有\(\mathrm O(n)\)查询，不好，还是三刷用Map_先扫一遍中序序列存着比较合适。