重建二叉树

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

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

TreeNode *reConstructBinaryTreeCore(
    vector<int>::iterator pre_begin, vector<int>::iterator pre_end,
    vector<int>::iterator vin_begin, vector<int>::iterator vin_end)
{
    if (pre_begin >= pre_end || vin_begin >= vin_end)
    {
        return NULL;
    }
    TreeNode *root = new TreeNode(*pre_begin);

    // find root in vin
    auto left_vin_begin = vin_begin;
    auto left_vin_end = vin_begin;
    while (left_vin_end < vin_end && *left_vin_end != *pre_begin){
        ++left_vin_end;
    }

    auto right_vin_begin = left_vin_end + 1;
    auto right_vin_end = vin_end;

    // split in pre
    auto left_pre_begin = pre_begin + 1;
    auto left_pre_end = left_pre_begin + (left_vin_end - left_vin_begin);
    auto right_pre_begin = left_pre_end;
    auto right_pre_end = pre_end;

    root->left = reConstructBinaryTreeCore(left_pre_begin, left_pre_end, left_vin_begin, left_vin_end);
    root->right = reConstructBinaryTreeCore(right_pre_begin, right_pre_end, right_vin_begin, right_vin_end);

    return root;
}

TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
    if (pre.size() <= 0 || vin.size() <= 0 || pre.size() != vin.size())
    {
        return NULL;
    }
    return reConstructBinaryTreeCore(pre.begin(), pre.end(), vin.begin(), vin.end());
}

TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
    if (pre.size() <= 0 || vin.size() <= 0 || pre.size() != vin.size()) {
        return NULL;
    }
    TreeNode *root = new TreeNode(pre[0]);

    for (int i = 0; i < vin.size(); i++) {
        if (vin[i] == pre[0]) {
            // 左子树，注意 copyOfRange 函数，左闭右开
            root->left = reConstructBinaryTree(
                vector<int>(pre.begin() + 1, pre.begin() + i + 1), 
                vector<int>(vin.begin(), vin.begin() + i));
            // 右子树，注意 copyOfRange 函数，左闭右开
            root->right = reConstructBinaryTree(
                vector<int>(pre.begin() + i + 1, pre.end()), 
                vector<int>(vin.begin() + i + 1, vin.end()));
            break;
        }
    }
    return root;
}