1. 程序员快看-教程，程序员编程资料站
  2. 首页
  3. leetcode刷题
  4. 正文

0106.从中序与后序遍历序列构造二叉树

分类：leetcode刷题    2024-03-04    阅读(129)

看完本文，可以一起解决如下两道题目

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

106.从中序与后序遍历序列构造二叉树

力扣题目链接

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

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

例如，给出

  • 中序遍历 inorder = [9,3,15,20,7]
  • 后序遍历 postorder = [9,15,7,20,3]
    返回如下的二叉树：

106. 从中序与后序遍历序列构造二叉树1

《代码随想录》算法视频公开课：坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

流程如图：

106.从中序与后序遍历序列构造二叉树

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

  • 第一步：如果数组大小为零的话，说明是空节点了。

  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

  • 第五步：切割后序数组，切成后序左数组和后序右数组

  • 第六步：递归处理左区间和右区间

不难写出如下代码：（先把框架写出来）

TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {

    // 第一步
    if (postorder.size() == 0) return NULL;

    // 第二步：后序遍历数组最后一个元素，就是当前的中间节点
    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);

    // 叶子节点
    if (postorder.size() == 1) return root;

    // 第三步：找切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }

    // 第四步：切割中序数组，得到 中序左数组和中序右数组
    // 第五步：切割后序数组，得到 后序左数组和后序右数组

    // 第六步
    root->left = traversal(中序左数组, 后序左数组);
    root->right = traversal(中序右数组, 后序右数组);

    return root;
}

难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。

此时应该注意确定切割的标准，是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。

在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭右闭，必然乱套！

我在数组：每次遇到二分法，都是一看就会，一写就废和数组：这个循环可以转懵很多人！中都强调过循环不变量的重要性，在二分查找以及螺旋矩阵的求解中，坚持循环不变量非常重要，本题也是。

首先要切割中序数组，为什么先切割中序数组呢？

切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。

中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，如下代码中我坚持左闭右开的原则：

// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
    if (inorder[delimiterIndex] == rootValue) break;
}

// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

接下来就要切割后序数组了。

首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。

后序数组的切割点怎么找？

后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。

此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。

中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

代码如下：

// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
postorder.resize(postorder.size() - 1);

// 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。

接下来可以递归了，代码如下：

root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);

完整代码如下：

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if (postorder.size() == 1) return root;

        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 切割中序数组
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割后序数组
        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

相信大家自己就算是思路清晰， 代码写出来一定是各种问题，所以一定要加日志来调试，看看是不是按照自己思路来切割的，不要大脑模拟，那样越想越糊涂。

加了日志的代码如下：（加了日志的代码不要在leetcode上提交，容易超时）

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorder.size() == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

        postorder.resize(postorder.size() - 1);

        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        // 以下为日志
        cout << "----------" << endl;

        cout << "leftInorder :";
        for (int i : leftInorder) {
            cout << i << " ";
        }
        cout << endl;

        cout << "rightInorder :";
        for (int i : rightInorder) {
            cout << i << " ";
        }
        cout << endl;

        cout << "leftPostorder :";
        for (int i : leftPostorder) {
            cout << i << " ";
        }
        cout << endl;
         cout << "rightPostorder :";
        for (int i : rightPostorder) {
            cout << i << " ";
        }
        cout << endl;

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

此时应该发现了，如上的代码性能并不好，因为每层递归定义了新的vector（就是数组），既耗时又耗空间，但上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。

下面给出用下标索引写出的代码版本：（思路是一样的，只不过不用重复定义vector了，每次用下标索引来分割）

class Solution {
private:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

那么这个版本写出来依然要打日志进行调试，打日志的版本如下：（该版本不要在leetcode上提交，容易超时）

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        cout << "----------" << endl;
        cout << "leftInorder :";
        for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "rightInorder :";
        for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "leftpostorder :";
        for (int i = leftPostorderBegin; i < leftPostorderEnd; i++) {
            cout << postorder[i] << " ";
        }
        cout << endl;

        cout << "rightpostorder :";
        for (int i = rightPostorderBegin; i < rightPostorderEnd; i++) {
            cout << postorder[i] << " ";
        }
        cout << endl;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

相关题目推荐

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

力扣题目链接

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

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

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

思路

本题和106是一样的道理。

我就直接给出代码了。

带日志的版本C++代码如下： （带日志的版本仅用于调试，不要在leetcode上提交，会超时）

class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        cout << "----------" << endl;
        cout << "leftInorder :";
        for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "rightInorder :";
        for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "leftPreorder :";
        for (int i = leftPreorderBegin; i < leftPreorderEnd; i++) {
            cout << preorder[i] << " ";
        }
        cout << endl;

        cout << "rightPreorder :";
        for (int i = rightPreorderBegin; i < rightPreorderEnd; i++) {
            cout << preorder[i] << " ";
        }
        cout << endl;


        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return NULL;
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());

    }
};

105.从前序与中序遍历序列构造二叉树，最后版本，C++代码：

class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return NULL;

        // 参数坚持左闭右开的原则
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

思考题

前序和中序可以唯一确定一棵二叉树。

后序和中序可以唯一确定一棵二叉树。

那么前序和后序可不可以唯一确定一棵二叉树呢？

前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。

举一个例子：

106.从中序与后序遍历序列构造二叉树2

tree1 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。

tree2 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。

那么tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！

所以前序和后序不能唯一确定一棵二叉树！

总结

之前我们讲的二叉树题目都是各种遍历二叉树，这次开始构造二叉树了，思路其实比较简单，但是真正代码实现出来并不容易。

所以要避免眼高手低，踏实地把代码写出来。

我同时给出了添加日志的代码版本，因为这种题目是不太容易写出来调一调就能过的，所以一定要把流程日志打出来，看看符不符合自己的思路。

大家遇到这种题目的时候，也要学会打日志来调试（如何打日志有时候也是个技术活），不要脑动模拟，脑动模拟很容易越想越乱。

最后我还给出了为什么前序和中序可以唯一确定一棵二叉树，后序和中序可以唯一确定一棵二叉树，而前序和后序却不行。

认真研究完本篇，相信大家对二叉树的构造会清晰很多。

其他语言版本

Java

106.从中序与后序遍历序列构造二叉树

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    
    }
    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
            if(inorder[middleIndex] == rootVal)
                break;
        }

        int leftInorderStart = inorderStart; 
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;


        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);
        int rightPostorderStart = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);

        return root;
    }  
}

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

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);

        return root;
    }
}

Python

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

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 第一步: 特殊情况讨论: 树为空. 或者说是递归终止条件
        if not preorder:
            return None

        # 第二步: 前序遍历的第一个就是当前的中间节点.
        root_val = preorder[0]
        root = TreeNode(root_val)

        # 第三步: 找切割点.
        separator_idx = inorder.index(root_val)

        # 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
        inorder_left = inorder[:separator_idx]
        inorder_right = inorder[separator_idx + 1:]

        # 第五步: 切割preorder数组. 得到preorder数组的左,右半边.
        # ⭐️ 重点1: 中序数组大小一定跟前序数组大小是相同的.
        preorder_left = preorder[1:1 + len(inorder_left)]
        preorder_right = preorder[1 + len(inorder_left):]

        # 第六步: 递归
        root.left = self.buildTree(preorder_left, inorder_left)
        root.right = self.buildTree(preorder_right, inorder_right)
        # 第七步: 返回答案
        return root

106.从中序与后序遍历序列构造二叉树

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # 第一步: 特殊情况讨论: 树为空. (递归终止条件)
        if not postorder:
            return None

        # 第二步: 后序遍历的最后一个就是当前的中间节点.
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 第三步: 找切割点.
        separator_idx = inorder.index(root_val)

        # 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
        inorder_left = inorder[:separator_idx]
        inorder_right = inorder[separator_idx + 1:]

        # 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
        # ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left): len(postorder) - 1]

        # 第六步: 递归
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
         # 第七步: 返回答案
        return root

Go

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var (
    hash map[int]int
)
func buildTree(inorder []int, postorder []int) *TreeNode {
    hash = make(map[int]int)
    for i, v := range inorder {  // 用map保存中序序列的数值对应位置
        hash[v] = i
    }
    // 以左闭右闭的原则进行切分
    root := rebuild(inorder, postorder, len(postorder)-1, 0, len(inorder)-1)
    return root
}
// rootIdx表示根节点在后序数组中的索引，l, r 表示在中序数组中的前后切分点
func rebuild(inorder []int, postorder []int, rootIdx int, l, r int) *TreeNode {
    if l > r {    // 说明没有元素，返回空树
        return nil
    }
    if l == r {  // 只剩唯一一个元素，直接返回
        return &TreeNode{Val : inorder[l]}
    }
    rootV := postorder[rootIdx]  // 根据后序数组找到根节点的值
    rootIn := hash[rootV]        // 找到根节点在对应的中序数组中的位置
    root := &TreeNode{Val : rootV}   // 构造根节点
    // 重建左节点和右节点
    root.Left = rebuild(inorder, postorder, rootIdx-(r-rootIn)-1, l, rootIn-1)
    root.Right = rebuild(inorder, postorder, rootIdx-1, rootIn+1, r)
    return root
}

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var (
    hash map[int]int
)
func buildTree(preorder []int, inorder []int) *TreeNode {
    hash = make(map[int]int, len(inorder))
    for i, v := range inorder {
        hash[v] = i
    }
    root := build(preorder, inorder, 0, 0, len(inorder)-1)  // l, r 表示构造的树在中序遍历数组中的范围
    return root
}
func build(pre []int, in []int, root int, l, r int) *TreeNode {
    if l > r {
        return nil
    }
    rootVal := pre[root]  // 找到本次构造的树的根节点
    index := hash[rootVal]  // 根节点在中序数组中的位置
    node := &TreeNode {Val: rootVal}
    node.Left = build(pre, in, root + 1, l, index-1)
    node.Right = build(pre, in, root + (index-l) + 1, index+1, r)
    return node
}

JavaScript

var buildTree = function(inorder, postorder) {
    if (!inorder.length) return null;
    const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal); // 创建中间节点
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
    return root;
};

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

var buildTree = function(preorder, inorder) {
  if (!preorder.length) return null;
  const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组第一个值
  const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
  const root = new TreeNode(rootVal); // 创建中间节点
  root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点
  root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点
  return root;
};

TypeScript

106.从中序与后序遍历序列构造二叉树

创建新数组:

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (postorder.length === 0) return null;
    const rootVal: number = postorder.pop()!;
    const rootValIndex: number = inorder.indexOf(rootVal);
    const rootNode: TreeNode = new TreeNode(rootVal);
    rootNode.left = buildTree(inorder.slice(0, rootValIndex), postorder.slice(0, rootValIndex));
    rootNode.right = buildTree(inorder.slice(rootValIndex + 1), postorder.slice(rootValIndex));
    return rootNode;
};

使用数组索引:

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    function recur(
        inorder: number[], postorder: number[],
        inBegin: number, inEnd: number,
        postBegin: number, postEnd: number
    ): TreeNode | null {
        if (postBegin === postEnd) return null;
        const rootVal: number = postorder[postEnd - 1]!;
        const rootValIndex: number = inorder.indexOf(rootVal, inBegin);
        const rootNode: TreeNode = new TreeNode(rootVal);

        const leftInorderBegin: number = inBegin;
        const leftInorderEnd: number = rootValIndex;
        const rightInorderBegin: number = rootValIndex + 1;
        const rightInorderEnd: number = inEnd;

        const leftPostorderBegin: number = postBegin;
        const leftPostorderEnd: number = postBegin + rootValIndex - inBegin;
        const rightPostorderBegin: number = leftPostorderEnd;
        const rightPostorderEnd: number = postEnd - 1;

        rootNode.left = recur(
            inorder, postorder,
            leftInorderBegin, leftInorderEnd,
            leftPostorderBegin, leftPostorderEnd
        );
        rootNode.right = recur(
            inorder, postorder,
            rightInorderBegin, rightInorderEnd,
            rightPostorderBegin, rightPostorderEnd
        );
        return rootNode;
    }
    return recur(inorder, postorder, 0, inorder.length, 0, inorder.length);
};

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

新建数组：

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) return null;
    const rootVal: number = preorder[0];
    const rootNode: TreeNode = new TreeNode(rootVal);
    const rootValIndex: number = inorder.indexOf(rootVal);
    rootNode.left = buildTree(preorder.slice(1, rootValIndex + 1), inorder.slice(0, rootValIndex));
    rootNode.right = buildTree(preorder.slice(rootValIndex + 1), inorder.slice(rootValIndex + 1));
    return rootNode;
};

使用数组索引:

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    function recur(
        preorder: number[], inorder: number[],
        preBegin: number, preEnd: number,
        inBegin: number, inEnd: number
    ): TreeNode | null {
        if (preBegin === preEnd) return null;
        const rootVal: number = preorder[preBegin];
        const rootNode: TreeNode = new TreeNode(rootVal);
        const rootValIndex: number = inorder.indexOf(rootVal, inBegin);

        const leftPreBegin: number = preBegin + 1;
        const leftPreEnd: number = preBegin + rootValIndex - inBegin + 1;
        const leftInBegin: number = inBegin;
        const leftInEnd: number = rootValIndex;

        const rightPreBegin: number = leftPreEnd;
        const rightPreEnd: number = preEnd;
        const rightInBegin: number = rootValIndex + 1;
        const rightInEnd: number = inEnd;

        rootNode.left = recur(preorder, inorder, leftPreBegin, leftPreEnd, leftInBegin, leftInEnd);
        rootNode.right = recur(preorder, inorder, rightPreBegin, rightPreEnd, rightInBegin, rightInEnd);
        return rootNode;
    };
    return recur(preorder, inorder, 0, preorder.length, 0, inorder.length);
};

C

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

int linearSearch(int* arr, int arrSize, int key) {
    int i;
    for(i = 0; i < arrSize; i++) {
        if(arr[i] == key)
            return i;
    }
    return -1;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    //若中序遍历数组中没有元素，则返回NULL
    if(!inorderSize)
        return NULL;
    //创建一个新的结点，将node的val设置为后序遍历的最后一个元素
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = postorder[postorderSize - 1];

    //通过线性查找找到中间结点在中序数组中的位置
    int index = linearSearch(inorder, inorderSize, postorder[postorderSize - 1]);

    //左子树数组大小为index
    //右子树的数组大小为数组大小减index减1（减的1为中间结点）
    int rightSize = inorderSize - index - 1;
    node->left = buildTree(inorder, index, postorder, index);
    node->right = buildTree(inorder + index + 1, rightSize, postorder + index, rightSize);
    return node;
}

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

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    // 递归结束条件：传入的数组大小为0
    if(!preorderSize)
        return NULL;

    // 1.找到前序遍历数组的第一个元素， 创建结点。左右孩子设置为NULL。
    int rootValue = preorder[0];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootValue;
    root->left = NULL;
    root->right = NULL;

    // 2.若前序遍历数组的大小为1，返回该结点
    if(preorderSize == 1)
        return root;

    // 3.根据该结点切割中序遍历数组，将中序遍历数组分割成左右两个数组。算出他们的各自大小
    int index;
    for(index = 0; index < inorderSize; index++) {
        if(inorder[index] == rootValue)
            break;
    }
    int leftNum = index;
    int rightNum = inorderSize - index - 1;

    int* leftInorder = inorder;
    int* rightInorder = inorder + leftNum + 1;

    // 4.根据中序遍历数组左右数组的各子大小切割前序遍历数组。也分为左右数组
    int* leftPreorder = preorder+1;
    int* rightPreorder = preorder + 1 + leftNum;

    // 5.递归进入左右数组，将返回的结果作为根结点的左右孩子
    root->left = buildTree(leftPreorder, leftNum, leftInorder, leftNum);
    root->right = buildTree(rightPreorder, rightNum, rightInorder, rightNum);

    // 6.返回根节点
    return root;
}

Swift

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

class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        return helper(preorder: preorder,
                      preorderBegin: 0,
                      preorderEnd: preorder.count,
                      inorder: inorder,
                      inorderBegin: 0,
                      inorderEnd: inorder.count)
    }

    func helper(preorder: [Int], preorderBegin: Int, preorderEnd: Int, inorder: [Int], inorderBegin: Int, inorderEnd: Int) -> TreeNode? {
        if preorderBegin == preorderEnd {
            return nil
        }

        // 前序遍历数组的第一个元素作为分割点
        let rootValue = preorder[preorderBegin]
        let root = TreeNode(rootValue)


        if preorderEnd - preorderBegin == 1 {
            return root
        }

        var index = 0 // 从中序遍历数组中找到根节点的下标
        if let ind = inorder.firstIndex(of: rootValue) {
            index = ind
        }

        // 递归
        root.left = helper(preorder: preorder,
                           preorderBegin: preorderBegin + 1,
                           preorderEnd: preorderBegin + 1 + index - inorderBegin,
                           inorder: inorder,
                           inorderBegin: inorderBegin,
                           inorderEnd: index)
        root.right = helper(preorder: preorder,
                            preorderBegin: preorderBegin + 1 + index - inorderBegin,
                            preorderEnd: preorderEnd,
                            inorder: inorder,
                            inorderBegin: index + 1,
                            inorderEnd: inorderEnd)
        return root
    }
}

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

class Solution_0106 {
    func buildTree(inorder: [Int], inorderBegin: Int, inorderEnd: Int, postorder: [Int], postorderBegin: Int, postorderEnd: Int) -> TreeNode? {
        if postorderEnd - postorderBegin < 1 {
            return nil
        }

        // 后序遍历数组的最后一个元素作为分割点
        let rootValue = postorder[postorderEnd - 1]
        let root = TreeNode(rootValue)

        if postorderEnd - postorderBegin == 1 {
            return root
        }

        // 从中序遍历数组中找到根节点的下标
        var delimiterIndex = 0
        if let index = inorder.firstIndex(of: rootValue) {
            delimiterIndex = index
        }

        root.left = buildTree(inorder: inorder,
                              inorderBegin: inorderBegin,
                              inorderEnd: delimiterIndex,
                              postorder: postorder,
                              postorderBegin: postorderBegin,
                              postorderEnd: postorderBegin + (delimiterIndex - inorderBegin))

        root.right = buildTree(inorder: inorder,
                               inorderBegin: delimiterIndex + 1,
                               inorderEnd: inorderEnd,
                               postorder: postorder,
                               postorderBegin: postorderBegin + (delimiterIndex - inorderBegin),
                               postorderEnd: postorderEnd - 1)
        return root
    }
}

Scala

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

object Solution {
  def buildTree(inorder: Array[Int], postorder: Array[Int]): TreeNode = {
    // 1、如果长度为0，则直接返回null
    var len = inorder.size
    if (len == 0) return null
    // 2、后序数组的最后一个元素是当前根元素
    var rootValue = postorder(len - 1)
    var root: TreeNode = new TreeNode(rootValue, null, null)
    if (len == 1) return root   // 如果数组只有一个节点，就直接返回
    // 3、在中序数组中找到切割点的索引
    var delimiterIndex: Int = inorder.indexOf(rootValue)
    // 4、切分数组往下迭代
    root.left = buildTree(inorder.slice(0, delimiterIndex), postorder.slice(0, delimiterIndex))
    root.right = buildTree(inorder.slice(delimiterIndex + 1, len), postorder.slice(delimiterIndex, len - 1))
    root   // 返回root，return关键字可以省略
  }
}

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

object Solution {
  def buildTree(preorder: Array[Int], inorder: Array[Int]): TreeNode = {
    // 1、如果长度为0，直接返回空
    var len = inorder.size
    if (len == 0) return null
    // 2、前序数组的第一个元素是当前子树根节点
    var rootValue = preorder(0)
    var root = new TreeNode(rootValue, null, null)
    if (len == 1) return root // 如果数组元素只有一个，那么返回根节点
    // 3、在中序数组中，找到切割点
    var delimiterIndex = inorder.indexOf(rootValue)

    // 4、切分数组往下迭代
    root.left = buildTree(preorder.slice(1, delimiterIndex + 1), inorder.slice(0, delimiterIndex))
    root.right = buildTree(preorder.slice(delimiterIndex + 1, preorder.size), inorder.slice(delimiterIndex + 1, len))

    root
  }
}

Rust

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

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if inorder.is_empty() {
            return None;
        }
        let mut postorder = postorder;
        let root = postorder.pop().unwrap();
        let index = inorder.iter().position(|&x| x == root).unwrap();
        let mut root = TreeNode::new(root);
        root.left = Self::build_tree(inorder[..index].to_vec(), postorder[..index].to_vec());
        root.right = Self::build_tree(inorder[index + 1..].to_vec(), postorder[index..].to_vec());
        Some(Rc::new(RefCell::new(root)))
    }
}

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

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if preorder.is_empty() {
            return None;
        }
        let root = preorder[0];
        let index = inorder.iter().position(|&x| x == root).unwrap();
        let mut root = TreeNode::new(root);
        root.left = Self::build_tree(preorder[1..index + 1].to_vec(), inorder[0..index].to_vec());
        root.right = Self::build_tree(
            preorder[index + 1..].to_vec(),
            inorder[index + 1..].to_vec(),
        );
        Some(Rc::new(RefCell::new(root)))
    }
}

C#

public TreeNode BuildTree(int[] inorder, int[] postorder)
{
    if (inorder.Length == 0 || postorder.Length == null) return null;
    int rootValue = postorder.Last();
    TreeNode root = new TreeNode(rootValue);
    int delimiterIndex = Array.IndexOf(inorder, rootValue);
    root.left = BuildTree(inorder.Take(delimiterIndex).ToArray(), postorder.Take(delimiterIndex).ToArray());
    root.right = BuildTree(inorder.Skip(delimiterIndex + 1).ToArray(), postorder.Skip(delimiterIndex).Take(inorder.Length - delimiterIndex - 1).ToArray());
    return root;
}