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

思路：

和Construct Binary Tree from Preorder and Inorder Traversal雷同，关键在于在inorder中找root，从而得以分割left/right subtree，并通过递归来重构。区别仅仅在于对postorder来说root为序列最后一个节点，以及left/right subtree左右边界index的计算稍有不同。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { if(inorder.size()!=postorder.size()) return NULL; int n = inorder.size(); return buildBT(inorder, postorder, 0, n-1, 0, n-1); } TreeNode *buildBT(vector<int> &inorder, vector<int> &postorder, int s1, int e1, int s2, int e2) { if(s1>e1 || s2>e2) return NULL; TreeNode *root = new TreeNode(postorder[e2]); int rootIndex = -1; for(int i=s1; i<=e1; i++) { if(inorder[i]==root->val) { rootIndex = i; break; } } if(rootIndex==-1) return NULL; int leftTreeSize = rootIndex - s1; int rightTreeSize = e1 - rootIndex; root->left = buildBT(inorder, postorder, s1, rootIndex-1, s2, s2+leftTreeSize-1); root->right = buildBT(inorder, postorder, rootIndex+1, e1, e2-rightTreeSize, e2-1); return root; } };