根据中序和后序遍历,构造二叉树,保证val不重复。注意别超内存
class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(inorder.size() <= 0 || postorder.size() <= 0) return NULL; TreeNode * root = buildTreeStep(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1); return root; } private: TreeNode *buildTreeStep(vector<int> &inorder,int ina,int inb,vector<int>&postorder,int poa,int pob) { if(ina > inb || poa > pob) return NULL; int root = postorder[pob]; int i; for(i = ina;i <= inb;i++) { if(inorder[i] == root)break; } //inleft: ina i-1 //inright:i+1 inb //poleft:poa,(i-1) - ina + poa //poright:(i-1) - ina + poa + 1,pob-1 TreeNode * node = new TreeNode(root); node->left = buildTreeStep(inorder,ina,i-1,postorder,poa,(i-1)-ina+poa); node->right = buildTreeStep(inorder,i+1,inb,postorder,(i-1) - ina+poa+1,pob-1); return node;<br /> } };