本文主要是介绍leetcode No105. Construct Binary Tree from Preorder and Inorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question:
Given preorder and inorder traversal of a tree, construct the binary tree.
根据树的前序遍历和中序遍历，构建二叉树
Algorithm：
前序遍历：根-左-右
中序遍历：左-根-右
举个例子
前序遍历：ABDECFG
中序遍历：DBEAFCG
1、前序遍历的第一个元素A，为根结点
2、在中序遍历找到A，则在中序遍历中A左边是左子树，右边是右子树
3、递归（左右子树同样如此）
Accepted Code：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return help(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}TreeNode* help(vector<int>& preorder,int begin1,int end1,vector<int>& inorder,int begin2,int end2){if(begin1>end1)return NULL;else if(begin1==end1)return new TreeNode(preorder[begin1]);TreeNode* root=new TreeNode(preorder[begin1]);int i;for(i=begin2;i<end2;i++)if(inorder[i]==preorder[begin1])break;int leftlen=i-begin2;//左右子树怎么分的举个例子就明白了root->left=help(preorder,begin1+1,begin1+leftlen,inorder,begin2,begin2+leftlen-1);root->right=help(preorder,begin1+leftlen+1,end1,inorder,begin2+leftlen+1,end2);return root;}
};
这篇关于leetcode No105. Construct Binary Tree from Preorder and Inorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
