重建二叉树

Introduction

Question：重建二叉树

Analysis

根据二叉树的性质，先序遍历和后序遍历的满足以下特点：

• 先序：[root, {left tree}, {right tree}]
• 中序：[{left tree}, root, {right tree}]

其中{left tree}和{right tree}表示左右子树的先/中序。

因此我们用先序的第一个元素构造出一个根节点，然后找到中序中对应根节点的位置，分割左右子树的先序和中序。这时递归求解左右子树即可。

Implement

typedef vector<int>::iterator vit;
TreeNode* reConstructBinaryTree(const vit &preBeg,const vit &preEnd,
                               const vit &vinBeg,const vit &vinEnd) {
    if (preBeg == preEnd) return nullptr;
    TreeNode *root = new TreeNode(*preBeg);

    const vit &it = find(vinBeg, vinEnd, *preBeg);
    auto size = it - vinBeg;
//         cout << root->val << size << endl;
    root->left = reConstructBinaryTree(preBeg + 1, preBeg + 1 + size,
                                      vinBeg, it);
    root->right = reConstructBinaryTree(preBeg + 1 + size, preEnd, it + 1, vinEnd);
    return root;
}

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    return reConstructBinaryTree(pre.begin(), pre.end(), vin.begin(), vin.end());
}