Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder 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>& inorder, vector<int>& postorder, int p,
11                              int q, int n, int m)
12 {
13     if((p>q)||(n>m))
14         return NULL;
15     int h=postorder[m];
16     TreeNode* hd=new TreeNode(h);
17     if(p==q)
18     {
19         return hd;
20     }
21     int index=p;
22     while(inorder[index]!=h)
23     {
24         index++;
25     }
26     int length=indexp;
27     TreeNode* left=buildTreeHelper(inorder,postorder,
                      p,p+length1,n,n+length1);
28     TreeNode* right=buildTreeHelper(inorder,postorder,
                      p+length+1,q,n+length,m1);
29     hd->left=left;
30     hd->right=right;
31     return hd;
32 }
33 class Solution {
34 public:
35     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
36         // Start typing your C/C++ solution below
37         // DO NOT write int main() function
38         int n=inorder.size();
39         return buildTreeHelper(inorder,postorder,0,n1,0,n1);
40     }
41 };
Advertisements
This entry was posted in Array and linked list, 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