（四）剑指offer之重建二叉树

题目描述：

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

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
        if(pre.empty() || in.empty())
            return NULL;
        return ConstructBinaryTree(pre.begin(),pre.end()-1,in.begin(),in.end()-1);
    }
    struct TreeNode* ConstructBinaryTree
    (vector<int>::iterator startPre,vector<int>::iterator endPre,
     vector<int>::iterator startIn,vector<int>::iterator endIn){
        int rootValue = *startPre;
        TreeNode* root = new TreeNode(rootValue);
        if(startPre == endPre){
            if(startIn == endIn && *startPre == *startIn)
                return root;
            else
                return NULL;
        }
        vector<int>::iterator rootInOrder = startIn;
        while(rootInOrder <= endIn && *rootInOrder != rootValue)
            ++rootInOrder;

        if(rootInOrder == endIn && *rootInOrder != rootValue)
            return NULL;

        int leftLength = rootInOrder - startIn;
        vector<int>::iterator leftPreEnd = startPre + leftLength;
        if(leftLength>0)
            root->left = ConstructBinaryTree(startPre+1,leftPreEnd,startIn,rootInOrder-1);
        if(leftLength < endIn - startIn)
            root->right = ConstructBinaryTree(leftPreEnd+1,endPre,rootInOrder+1,endIn);

        return root;
    }
};

如有建议或其他问题，可随时给我们留言。或者到以下链接：

https://github.com/gaobaoru/code_day

Star/Fork/Push 您的代码，开源仓库需要您的贡献。
请查看Coding 题目网址和收藏Accepted代码仓库，进行coding！！！