首页 > 代码库 > 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 return get_Tree(preorder.begin(),preorder.end(),inorder.begin(),inorder.end()); 5 } 6 TreeNode * get_Tree(vector<int>::iterator pre_l,vector<int>::iterator pre_r,vector<int>::iterator in_l, vector<int>::iterator in_r){ 7 if(pre_l >= pre_r || in_l >= in_r) return NULL; 8 TreeNode * root = new TreeNode(*pre_l); 9 vector<int>::iterator loca = find(in_l,in_r,*pre_l);10 if(loca == in_l) {11 root->right = get_Tree(next(pre_l),pre_r,next(loca),in_r);12 }else if(loca == prev(in_r)){13 root->left = get_Tree(next(pre_l),pre_r,in_l,loca);14 }else{15 root->left = get_Tree(next(pre_l),next(pre_l,distance(in_l,loca)+1),in_l,loca);16 root->right = get_Tree(next(pre_l,distance(in_l,loca)+1),pre_r,next(loca),in_r);17 }18 return root;19 }20 };
其实loca == in_l及loca == prev(in_r)的情况可以包含在第三种情况中，所以代码可以简化为：
1 class Solution { 2 public: 3 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { 4 return get_Tree(preorder.begin(),preorder.end(),inorder.begin(),inorder.end()); 5 } 6 TreeNode * get_Tree(vector<int>::iterator pre_l,vector<int>::iterator pre_r,vector<int>::iterator in_l, vector<int>::iterator in_r){ 7 if(pre_l >= pre_r || in_l >= in_r) return NULL; 8 TreeNode * root = new TreeNode(*pre_l); 9 vector<int>::iterator loca = find(in_l,in_r,*pre_l);10 root->left = get_Tree(next(pre_l),next(pre_l,distance(in_l,loca)+1),in_l,loca);11 root->right = get_Tree(next(pre_l,distance(in_l,loca)+1),pre_r,next(loca),in_r);12 return root;13 }14 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。