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