Wednesday, February 27, 2013

Construct Binary Tree from Inorder and Postorder Traversal


/*

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

*/
/**
 * 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