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

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

题目考察的知识点

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

题目解答方法的文字分析

解决这道题的关键在于先序遍历的特点和中序遍历的划分，通过不断递归构建子树，最终完成整个二叉树的构建。

1. 首先，从先序遍历数组中找到根节点，即第一个元素。
2. 在中序遍历数组中找到根节点的位置，将数组分为左子树和右子树两部分。
3. 根据左子树的节点数量，划分先序遍历数组为根节点、左子树和右子树三部分。
4. 递归构建左子树和右子树，重复上述过程，直到构建完成整个二叉树。

这个过程在每个递归中都是类似的，通过处理先序和中序数组，不断缩小问题规模，最终构建出整个二叉树的结构。

思路示例：

考虑以下先序遍历和中序遍历：

先序遍历：[3, 9, 20, 15, 7]中序遍历：[9, 3, 15, 20, 7]

根据先序遍历，根节点是 3。在中序遍历中，根节点将数组分为左子树 [9] 和右子树 [15, 20, 7]。然后我们可以对左子树和右子树分别递归构建，最终完成整个二叉树的构建。

本题解析所用的编程语言

本题解析所用的编程语言是 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* buildTreeII(vector<int>& preOrder, vector<int>& inOrder) {
        return buildTreeHelper(preOrder, inOrder, 0, preOrder.size() - 1, 0, inOrder.size() - 1);
    }

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

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

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

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

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

        return root;
    }
};

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