Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

1:注意特殊情况。2:递归的情况；3:递归结束情况；4:首先获得根节点，之后把两个数组分别分成两部分，递归分别得出左子树和右子树。

TreeNode *buildTree(vector
     
       &preorder, vector
      
        &inorder)    {        if(preorder.size() == 0 || inorder.size() == 0 || preorder.size() != inorder.size())        {            return NULL;        }                int size = (int)preorder.size();                return buildTreeCore(preorder, 0, inorder, 0, size);    }        TreeNode* buildTreeCore(vector
       
         &preorder, int preStart,  vector
        
          &inorder, int preIn, int length)    {        if(length == 1)        {            if(preorder[preStart] != inorder[preIn])            {                return NULL;            }        }                int rootValue = preorder[preStart];        TreeNode *root = new TreeNode(rootValue);                int i = 0;                for(; i < length; i++)        {            if(inorder[preIn + i] == rootValue)            {                break;            }        }                if(i == length)        {            return NULL;        }                if(i > 0)        {            root->left = buildTreeCore(preorder, preStart + 1, inorder, preIn, i);        }                if(i < length - 1)        {            root->right = buildTreeCore(preorder, preStart + i + 1, inorder, preIn + i + 1, length - 1 - i);        }                        return root;    }
        
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。