Construct Binary Tree from Preorder and Inorder Traversal

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

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

C++:
01 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10  TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder,
11                            int p, int q, int n, int m)
12 {
13     if((p>q)||(n>m))
14         return NULL;
15     int h=preorder[p];
16     TreeNode* head=new TreeNode(h);
17     if(p==q)
18     {
19         return head;
20     }
21     int index=n;
22     while(inorder[index]!=h)
23     {
24         index++;
25     }
26     int length=indexn;
27     TreeNode* left=buildTreeHelper(preorder,inorder,
28                                    p+1,p+length,n,n+length1);
29     TreeNode* right=buildTreeHelper(preorder,inorder,
30                                     p+length+1,q,n+length+1,m);
31     head->left=left;
32     head->right=right;
33     return head;
34 }
35 class Solution {
36 public:
37     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
38         // Start typing your C/C++ solution below
39         // DO NOT write int main() function
40         int size=preorder.size();
41         return buildTreeHelper(preorder,inorder,0,size1,0,size1);
42     }
43 };
Advertisements
This entry was posted in Array and linked list, Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s