根据前序序列和中序序列构建二叉树

前序序列和中序序列构建二叉树

简介

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例子

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

代码

class Solution
{
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int len = inorder.size();
        if (preorder.empty() || inorder.empty()) // 序列为空
            return nullptr;
        TreeNode *root = new TreeNode(preorder[0]); // 创建根节点
        int index = 0;                              // 中序序列中根节点的位置
        while (preorder[0] != inorder[index])
            index++;                                             // 在中序序列中查找根结点位置
        preorder.erase(preorder.begin());                        // 移除先序序列中第一个元素
        vector<int>::iterator inorderiterator = inorder.begin(); // 中序遍历迭代器
        vector<int> inorderleft, inorderright;
        if (index != 0)                                                             // index != 0 说明存在左子树
            inorderleft = vector<int>(inorderiterator, inorderiterator + index);    // 左子树中序遍历
        if (index != len - 1)                                                       // 存在右子树
            inorderright = vector<int>(inorderiterator + index + 1, inorder.end()); //　右子树中序遍历
        root->left = buildTree(preorder, inorderleft);                              // 构建左子树
        root->right = buildTree(preorder, inorderright);                            // 构建右子树
        return root;                                                                // 返回构建好的树
    }
};

参考

由前序遍历和中序遍历树构造二叉树