[leetcode] 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.

// in inorder traversal sequence, the nodes are organized as [left] [root] [right]
// in postorder traversal sequence, the nodes are organized as [left] [right] [root]
// construct the original tree recursively. 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return _buildTree(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }
    TreeNode * _buildTree(vector<int>::iterator inorderStart, vector<int>::iterator inorderEnd, vector<int>::iterator postorderStart, vector<int>::iterator postorderEnd){
        //base condition
        if(inorderStart == inorderEnd){
            return NULL;
        }
        int vRoot = *(postorderEnd - 1);
        int i = 0;
        while(*(inorderStart + i) != vRoot){
            i++;
        }
        TreeNode * root = new TreeNode(vRoot);
        root->left = _buildTree(inorderStart, inorderStart + i, postorderStart, postorderStart + i);
        root->right = _buildTree(inorderStart + i + 1, inorderEnd, postorderStart + i, postorderEnd - 1);
        return root;
    }
};

Untitled

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.