首页 > 代码库 > LeetCode:Construct Binary Tree from Preorder and Inorder Traversal
LeetCode: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.
解题思路:先序遍历的第一个元素为根元素,在中序遍历序列中找到根元素的位置。中序遍历根元素左边为左子树中序遍历序列,右边为右子树中序遍历序列。根据左右子树中序遍历序列的长度可以将先序遍历序列分割成左右两部分,左边为左子树的先序遍历序列,右边为右子树的先序遍历序列。此时左右子树的先序序列和中序序列都已知,对左右子树递归地调用上述方法,即可得结果。
代码:
TreeNode * build_tree(vector<int>::iterator prel,vector<int>::iterator prer,vector<int>::iterator inl,vector<int>::iterator inr) { if(prel >= prer) return NULL; TreeNode * root; if(prer - prel == 1) { root = new TreeNode(0); root->val = *prel; return root; } root = new TreeNode(0); root->val = *prel; vector<int>::iterator root_pos = find(inl,inr,root->val); int left_length = root_pos - inl; root->left = build_tree(prel+1,prel+1+left_length,inl,inl+left_length); root->right = build_tree(prel+1+left_length,prer,inl+left_length+1,inr); return root; } TreeNode * Solution::buildTree(vector<int> &preorder, vector<int> &inorder) { return build_tree(preorder.begin(),preorder.end(),inorder.begin(),inorder.end()); }
LeetCode:Construct Binary Tree from Preorder and Inorder Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。