LeetCode 剑指offer 面试题07. 重建二叉树

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 通过前序确定根节点 然后通过中序划分左子树具有的元素 右子树具有的元素 然后递归
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())return NULL;
        else return buildTreeHelper(preorder,inorder,0,preorder.size(),0,inorder.size());
    }
    TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder,int ps,int pe,int is,int ie)
    {
        TreeNode* node=new TreeNode(preorder[ps]);
        int cur;
        for(cur=is;cur<ie;cur++)if(inorder[cur]==preorder[ps])break;
        int left_size=cur-is,right_size=ie-cur-1;
        if(left_size)
            node->left=buildTreeHelper(preorder,inorder,ps+1,ps+1+left_size,is,cur);
        if(right_size)
            node->right=buildTreeHelper(preorder,inorder,pe-right_size,pe,cur+1,ie);
        return node;
    }
};