Given inorder and postorder traversal of a tree

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 个答案

class Solution { public: TreeNode *buildTree(vector &inorder, vector &postorder) { vector::size_type lenIn = inorder.size(); vector::size_type lenPost = postorder.size(); return buildTree_Aux(inorder,0,lenIn-1,postorder,0,lenPost-1); } TreeNode *buildTree_Aux(vector &inorder,int inB,int inE, vector &postorder,int poB,int poE) { if(inB > inE || poB > poE) return NULL; //在后序遍历中确定根节点 TreeNode* root = new TreeNode(postorder[poE]); //在中序遍历中确定左右子树 vector::iterator iter = find(inorder.begin()+inB,inorder.begin()+inE,postorder[poE]); int index = iter - inorder.begin(); root->left = buildTree_Aux(inorder,inB,index-1,postorder,poB,poB+index-1-inB); root->right = buildTree_Aux(inorder,index+1,inE,postorder,poB+index-inB,poE-1); return root; } };

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目