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

考察的知识点：二叉树的构建和遍历；

解答方法分析：

1. 在buildTree函数中，首先判断输入数组是否为空或长度不相等，如果是，则返回空指针。
2. 调用buildTreeHelper函数进行具体的构建操作。
3. 在buildTreeHelper函数中，参数inOrder表示中序遍历的数组，参数inStart和inEnd表示当前处理中序遍历数组的起始和结束位置，postOrder表示后序遍历的数组，参数postStart和post表示当前处理后序遍历数组的起始位置和结束位置。
4. 首判断递归结束的条件，即inStart大于inEnd或postStart大于postEnd，如果是，则返回空指针。
5. 获取当前子树的根节点值，即后序遍历数组的最后一个元素postOrder[postEnd]。
6. 创建根节点对象赋值为当前根节点值。
7. 在中序遍历数组中找根节点的位置rootIndex。
8. 利用rootIndex将中遍历数组分为左子树和子树的部分。
9. 递归地构建左子树，即调用buildTreeHelper函数入左子树的中序遍历数组和后序遍历数组的起始位置和结束位置，将返回结果作为当前根节点的左子节点。
10. 递归地构建右子树，即调用buildTreeHelper函数传入右子树的中序遍历数组和后序历数组的起始位置结束位置，将返回结果作为当前根节点的右子节点。
11. 返回根节点。

所用编程语言：C++；

完整编程代码：↓

/**
 * 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) {
        if (preOrder.empty() || inOrder.empty() || preOrder.size() != inOrder.size()) {
            return nullptr;
        }

        return buildTreeIIHelper(preOrder, 0, preOrder.size() - 1, inOrder, 0,
                                 inOrder.size() - 1);
    }

    TreeNode* buildTreeIIHelper(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);

        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inOrder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        int leftLength = rootIndex - inStart;

        root->left = buildTreeIIHelper(preOrder, preStart + 1, preStart + leftLength,
                                       inOrder, inStart, rootIndex - 1);
        root->right = buildTreeIIHelper(preOrder, preStart + leftLength + 1, preEnd,
                                        inOrder, rootIndex + 1, inEnd);

        return root;
    }
};