题解 | #重建二叉树#

/*
描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
复制
返回值：
{1,2,5,3,4,6,7}

*/

#include<iostream>
#include<map>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& pre, vector<int>& vin) {
        preidx = 0;
        for (int i = 0; i < vin.size(); ++i)
            midmap[vin[i]] = i;
        TreeNode* root = helper(pre, vin, 0, pre.size() - 1);
        return root;
    }

private:
    map<int, int> midmap;
    int preidx;

    TreeNode* helper(vector<int>& pre, vector<int>& vin, int low, int high) {
        if (low > high) return nullptr;
        TreeNode* root = new TreeNode(pre[preidx]);
        int index = midmap[pre[preidx]];
        preidx++;
        root->left = helper(pre, vin, low, index - 1);
        root->right = helper(pre, vin, index + 1, high);
        return root;
    }
};


void printTreeMid(TreeNode* root) {
    if (root == NULL)return;
    printTreeMid(root->left);
    cout << root->val << " ";
    printTreeMid(root->right);
}

void printTreePre(TreeNode* root) {
    if (root == NULL)return;
    cout << root->val << " ";
    printTreePre(root->left);
    printTreePre(root->right);
}


int main() {
    vector<int> pre({ 1,2,3,4,5,6,7 });
    vector<int> mid({ 3,2,4,1,6,5,7 });
    Solution sol;
    TreeNode* root = sol.reConstructBinaryTree(pre, mid);
    printTreePre(root);
    cout << endl;
    printTreeMid(root);

    return 0;
}