Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
- For example, given
- inorder = [9,3,15,20,7]
- postorder = [9,15,7,20,3]
- Return the following binary tree:
- 3
- / 9 20
- / 15 7
- class Solution {
- public:
- TreeNode*buildchild(vector<int>& postorder, vector<int>& inorder,int p1,int p2, int i1, int i2) {
- if (i2 <i1)
- return NULL;
- int nowroot = postorder[p2];
- TreeNode*ans = new TreeNode(nowroot);
- for (int i = i1; i <= i2; i++)
- if (inorder[i] == nowroot) {
- int left = i - i1, right = i2 - i;
- if (i != i1)
- ans->left = buildchild(postorder, inorder,p1,p1+left-1, i1, i - 1);
- if (i != i2)
- ans->right = buildchild(postorder, inorder, p1 + left, p2 - 1, i + 1, i2);
- }
- return ans;
- }
- TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
- return buildchild(postorder, inorder, 0,postorder.size()-1,0, inorder.size() - 1);
- }
- };
- View Code
来源: http://www.bubuko.com/infodetail-2976381.html