Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
解题思路： 同105. Construct Binary Tree from Preorder and Inorder Traversal。
/** * 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(begin(inorder), end(inorder), begin(postorder), end(postorder)); } template <typename InputIterator> TreeNode* buildTree(InputIterator in_first, InputIterator in_last, InputIterator post_first, InputIterator post_last) { if (in_first == in_last) return nullptr; if (post_first == post_last) return nullptr; auto root = new TreeNode(*prev(post_last)); auto inRootPos = find(in_first, in_last, *prev(post_last)); auto leftSize = distance(in_first, inRootPos); root->left = buildTree(in_first, inRootPos, post_first, next(post_first, leftSize)); root->right = buildTree(next(inRootPos), in_last, next(post_first, leftSize), prev(post_last)); return root; } };