剑指offer--19.重建二叉树

先序：根》左》右

中序：左》根》右

后序：左》右》根

e.g.

{1,2,4,7,3,5,6,8}

{4,7,2,1,5,3,8,6}

先序第一个元素是根节点，在中序中找到后，中序左边的是左子树，右边是右子树

----------------------------------------------------------------------------------------------------

时间限制：1秒 空间限制：32768K 热度指数：571383

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {
            if(in.size() == 0) return NULL;
            vector<int> pre_left,pre_right,in_left,in_right;
            int start = pre[0], pos;
            for( pos=0; pos<in.size(); pos++) {
                if(in[pos] == start) break;
            }
            for(int i=0; i<in.size(); i++) {
                if( i<pos) {
                    in_left.push_back(in[i]);
                    pre_left.push_back(pre[i+1]);
                } else if(i>pos) {
                    in_right.push_back(in[i]);
                    pre_right.push_back(pre[i]);
                }
            }
            TreeNode* node = new TreeNode(start);
            node->left = reConstructBinaryTree(pre_left, in_left);
            node->right = reConstructBinaryTree(pre_right, in_right);
            return node;
        }
};