首页 > 代码库 > Construct Binary Tree from Inorder and Postorder Traversal
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 class Solution { 2 public: 3 TreeNode *buildTree( vector<int> &inorder, vector<int> &postorder ) { 4 if( inorder.empty() || inorder.size() != postorder.size() ) { return 0; } 5 return BuildSub( inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1 ); 6 } 7 private: 8 TreeNode *BuildSub( vector<int> &inorder, int inStart, int inEnd, vector<int> &postorder, int postStart, int postEnd ) { 9 if( inStart > inEnd ) { return 0; }10 int index = 0;11 while( postorder[postEnd] != inorder[inStart+index] ) { ++index; }12 TreeNode *treeNode = new TreeNode( inorder[inStart+index] );13 treeNode->left = BuildSub( inorder, inStart, inStart+index-1, postorder, postStart, postStart+index-1 );14 treeNode->right = BuildSub( inorder, inStart+index+1, inEnd, postorder, postStart+index, postEnd-1 );15 return treeNode;16 }17 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。