Tuesday, November 11, 2014

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

 ``` 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 &inorder, vector &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 &inorder, vector &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; } }; ```