首页 > 代码库 > 前序遍历和中序遍历树构造二叉树
前序遍历和中序遍历树构造二叉树
前序遍历和中序遍历树构造二叉树
根据前序遍历和中序遍历树构造二叉树.
注意事项
你可以假设树中不存在相同数值的节点
样例
给出中序遍历:[1,2,3]
和前序遍历:[2,1,3]
. 返回如下的树:
2
/ 1 3
标签
二叉树
1 /** 2 * Definition of TreeNode: 3 * class TreeNode { 4 * public: 5 * int val; 6 * TreeNode *left, *right; 7 * TreeNode(int val) { 8 * this->val = val; 9 * this->left = this->right = NULL; 10 * } 11 * } 12 */ 13 14 15 class Solution { 16 /** 17 *@param preorder : A list of integers that preorder traversal of a tree 18 *@param inorder : A list of integers that inorder traversal of a tree 19 *@return : Root of a tree 20 */ 21 public: 22 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { 23 // write your code here 24 TreeNode *root = NULL; 25 vector<int> preorder_l,preorder_r,inorder_l,inorder_r; 26 int i,root_index=0; 27 28 if(preorder.empty()!=1 || inorder.empty()!=1) { 29 root = new TreeNode(preorder[0]); // 在前序队列中找根节点 30 31 // 在中序队列中找出根节点位置 32 for(i=0; i<inorder.size(); i++) { 33 if(preorder[0] == inorder[i]) 34 break; 35 root_index++; 36 } 37 38 // 左右子树的前序、中序队列 39 for(i=0; i<root_index; i++) { 40 preorder_l.push_back(preorder[i+1]); 41 inorder_l.push_back(inorder[i]); 42 } 43 for(i=root_index+1; i<inorder.size(); i++) { 44 preorder_r.push_back(preorder[i]); 45 inorder_r.push_back(inorder[i]); 46 } 47 48 root->left = buildTree(preorder_l, inorder_l); 49 root->right = buildTree(preorder_r, inorder_r); 50 } 51 return root; 52 } 53 };
前序遍历和中序遍历树构造二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。