Construct Binary Tree from Inorder and Postorder Traversal

LeetCode #106

Description:

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

Example:

Note

Idea:

见Construct Binary Tree from Preorder and Inorder Traversal 思路几乎一样，就是对于postorder来说，root是最后一个。

Code:

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
    }

    template<typename T>
    TreeNode* buildTree(T post_begin, T post_end, T in_begin, T in_end){
        if(post_begin==post_end) return NULL; // 到底了，return NULL
        if(in_begin==in_end) return NULL;

        TreeNode* root = new TreeNode(*prev(post_end)); // for postorder, the root is in the end
        auto it_root_inorder = find(in_begin, in_end, *prev(post_end));
        int left_size = it_root_inorder-in_begin; // Left subtree size
        int right_size = in_end-it_root_inorder-1; // right subtree size

        root->left = buildTree(post_begin, next(post_begin, left_size), in_begin, it_root_inorder);
        root->right = buildTree(next(post_begin, left_size), prev(post_end), next(it_root_inorder), in_end);

        return root;
    }
};