首页 > 代码库 > 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.
思路：递归。主要是注意调用时起始和终止的index。
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 TreeNode* root=process(preorder, 0,preorder.size(),inorder,0,inorder.size());14 return root;15 }16 TreeNode* process(vector<int> &preorder, int s1, int e1, vector<int> &inorder, int start, int end)17 {18 if(start>=end)19 {20 return NULL;21 }22 int root_val=preorder[s1];23 int inorder_index=start;24 while(inorder_index<end)25 {26 if(inorder[inorder_index]==root_val)27 break;28 else inorder_index++;29 }30 int count=inorder_index-start;//做子树节点数量31 TreeNode* left=process(preorder, s1+1,s1+count+1,inorder,start,inorder_index);32 TreeNode* right=process(preorder,s1+count+1, e1,inorder, inorder_index+1,end);33 TreeNode* root=new TreeNode(root_val);34 root->left=left;35 root->right=right;36 return root;37 }38 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。