题解 | #牛群的树形结构重建#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了二叉树的构建和遍历，需要根据中序遍历和后序遍历的结果重建二叉树。

题目解答方法的文字分析

我们可以使用递归的方式来解决这个问题。对于后序遍历来说，最后一个元素是根节点，在中序遍历中，根节点将中序遍历分为左子树和右子树两部分。我们可以根据这个特点来递归构建二叉树。

1. 首先，找到后序遍历数组的最后一个元素，它是树的根节点。
2. 在中序遍历数组中找到根节点的位置，将数组分为左子树和右子树两部分。
3. 递归地对左子树和右子树进行构建，分别得到左子树的根节点和右子树的根节点。
4. 将左子树的根节点连接到根节点的左子树上，将右子树的根节点连接到根节点的右子树上。
5. 返回根节点。

这个过程在每个递归中都是类似的，不断缩小问题规模，直到最终构建完成整个二叉树。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        return buildTreeHelper(inOrder, postOrder, 0, inOrder.size() - 1, 0, postOrder.size() - 1);
    }

    TreeNode* buildTreeHelper(vector<int>& inOrder, vector<int>& postOrder, int inStart, int inEnd, int postStart, int postEnd) {
        // 如果中序遍历数组的起始索引大于终止索引，或者后序遍历数组的起始索引大于终止索引，说明已经处理完所有节点，返回 nullptr
        if (inStart > inEnd || postStart > postEnd) {
            return nullptr;
        }

        // 创建当前子树的根节点，值为后序遍历数组的最后一个元素
        TreeNode* root = new TreeNode(postOrder[postEnd]);
        int rootIndex = inStart;

        // 在中序遍历数组中寻找根节点的位置，用于划分左子树和右子树
        while (rootIndex <= inEnd && inOrder[rootIndex] != root->val) {
            rootIndex++;
        }

        // 计算左子树的节点数量
        int leftSubtreeSize = rootIndex - inStart;

        // 递归构建左子树和右子树，根据中序和后序数组的特点来确定索引范围
        root->left = buildTreeHelper(inOrder, postOrder, inStart, rootIndex - 1, postStart, postStart + leftSubtreeSize - 1);
        root->right = buildTreeHelper(inOrder, postOrder, rootIndex + 1, inEnd, postStart + leftSubtreeSize, postEnd - 1);

        return root;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！