105_buildTree.txt

//递归构建
//1.如果前序遍历或中序遍历为空，则二叉树为空直接返回
//2.首先构建根结点为前序遍历的第一个元素
//3.从中序遍历中找到根节点元素然后左边的为左子树，右边的为右子树
//4.递归构建左右子树

/**
 * 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.size()==0 || inorder.size()==0)
            return NULL;
        return helper(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
    TreeNode* helper(vector<int>& preorder,int pre_begin,int pre_end,vector<int>& inorder,int in_begin,int                          in_end){
        TreeNode* root = new TreeNode(preorder[pre_begin]);//构建根节点
        root->left = NULL;
        root->right = NULL;
        int i = in_begin;
        while(i<=in_end && inorder[i]!= root->val)//在中序遍历中找到根结点
            i++;
        int l = i-in_begin;//此时左边子树的长度
        int r = in_end-i;//此时右边子树的长度
        if(l>0)//递归构建左子树
            root->left = helper(preorder,pre_begin+1,pre_begin+l,inorder,in_begin,in_begin+l-1);
        if(r>0)
            root->right = helper(preorder,pre_begin+l+1,pre_end,inorder,in_begin+l+1,in_end);
        return root;
    }
};