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.
拿上一题的代码来改的,然后发现拷贝粘贴果然是第一BUG源。。。
/** * Definition for binary tree * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function int psz=postorder.size(),isz=inorder.size(); assert(psz==isz); return create(postorder,0,psz-1,inorder,0,isz-1); } TreeNode* create(vector<int>& post,int pl,int pr,vector<int>& in,int il,int ir) { if ( pl>pr ) { assert(il>ir); return NULL; } int val=post[pr]; int pos=il; for(;pos<=ir;pos++) if ( in[pos]==val) break; assert(pos<=ir); TreeNode* root=new TreeNode(val); int ln=pos-il; int rn=ir-pos; root->left=create(post,pl,pl+ln-1,in,il,pos-1); root->right=create(post,pl+ln,pr-1,in,pos+1,ir); return root; } };