【剑指Offer笔记】：重建二叉树

题目描述

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

递归法一：

class Solution
{
public:
struct TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> in)
{
// 长度不能为0
if (pre.size() == 0)
return NULL;

    int length = pre.size();
    int value = pre[0]; //  前序遍历的第一个结点是根节点
    TreeNode *root = new TreeNode(value);

    if (pre.size() == 1)
        return root;

    //  在中序遍历中查找到根的位置
    int rootIndex = 0;
    while (rootIndex < length)
    {
        if (in[rootIndex] == value)
        {
            break;
        }
        rootIndex++;
    }

    ///  确定左右子树的长度
    int leftLength = rootIndex;
    int rightLength = length - 1 - rootIndex; //还要减去根，所以还要减去1

    vector<int> preLeft(leftLength);   //左子树的前序序列
    vector<int> inLeft(leftLength);    //左子树的中序序列
    vector<int> preRight(rightLength); //右子树的前序序列
    vector<int> inRight(rightLength);  //右子树的中序序列

    for (int i = 0; i < length; i++)
    {
        if (i < rootIndex)
        {
            //  前序遍历的第一个是根节点, 根后面的(leftLegnth = rootIndex) - 1个节点是左子树, 因此是i+1
            preLeft[i] = pre[i + 1];
            //  中序遍历前(leftLength = rootIndex) - 1个节点是左子树, 第rootIndex个节点是根
            inLeft[i] = in[i];
        }
        else if (i > rootIndex)
        {
            //  前序遍历的第一个是根节点, 根后面的(leftLegnth = rootIndex) - 1个节点是左子树, 后面是右子树
            preRight[i - rootIndex - 1] = pre[i];
            //  中序遍历前(leftLength = rootIndex) - 1个节点是左子树, 第rootIndex个节点是根, 然后是右子树
            inRight[i - rootIndex - 1] = in[i];
        }
    }

    root->left = reConstructBinaryTree(preLeft, inLeft);
    root->right = reConstructBinaryTree(preRight, inRight);

    return root;
}

};

牛客网在线检验：重建二叉树_牛客网

参考资料：http://blog.csdn.net/gatieme/article/details/51108612