/*
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
You may assume that duplicates do not exist in the tree
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int searchTree(vector<int> inorder, int value){
for(int i=0; i<inorder.size(); i++){
if(inorder[i]==value){
return i;
}
}
return -1;
}
TreeNode *buildSubTree(vector<int> inorder, vector<int> postorder, int & n, int lowIdx, int highIdx){
if(lowIdx > highIdx) return NULL;
if(n<0) return NULL;
TreeNode *node;
node = new TreeNode(postorder[n]);
n--;
if(lowIdx == highIdx) return node;
int index = searchTree(inorder, node->val);
node->right = buildSubTree(inorder, postorder, n, index+1, highIdx);
node->left = buildSubTree(inorder, postorder, n, lowIdx, index-1);
return node;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = inorder.size();
if (size != postorder.size()) return NULL;
if (size == 0) return NULL;
int n = size-1;
return buildSubTree(inorder, postorder, n, 0, size-1);
}
};
No comments:
Post a Comment