首页 > 代码库 > 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 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { 13 if(preorder.size()!=inorder.size()) return NULL; 14 return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1); 15 } 16 17 TreeNode *build(vector<int> &preorder, vector<int> &inorder,int s1,int e1,int s2,int e2){ 18 if(s1>e1||s2>e2) return NULL; 19 if(s1==e1) return new TreeNode(preorder[s1]); 20 TreeNode *res=new TreeNode(preorder[s1]); 21 int tmp=preorder[s1]; 22 int index=0; 23 while((s2+index)<=e2){ 24 if(inorder[s2+index]==tmp) 25 break; 26 index++; 27 } 28 res->left=build(preorder,inorder,s1+1,s1+index,s2,s2+index-1); 29 res->right=build(preorder,inorder,s1+index+1,e1,s2+index+1,e2); 30 return res; 31 } 32 };
construct-binary-tree-from-preorder-and-inorder-traversal——前序和中序求二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。