leetcode练习题 construct-binary-tree-from-preorder-and-inorder-traversal

解题思路

前序遍历第一个结点为根，在中序遍历中找到该结点，从而将中序遍历分为左右子树，准确定位左右子树在前序遍历中的起点和终点，之后递归建立左右子树，设置递归出口，最后返回根。

代码

class Solution {
public:TreeNode *buildTree(vector<int> &preorder,vector<int> &inorder,int prestart,int preend,int instart,int inend){if(prestart > preend || instart > inend)return NULL;TreeNode *root = new TreeNode(preorder[prestart]);int flag = 0;for(int i = instart;i <= inend;i++){if(inorder[i] == preorder[prestart]){flag = i;break;}}root->left = buildTree(preorder,inorder,prestart + 1,prestart + flag - instart,instart,flag - 1);root->right = buildTree(preorder,inorder,prestart + flag - instart + 1,preend,flag + 1,inend);return root;}TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {return buildTree(preorder,inorder,0,preorder.size() - 1,0,inorder.size() - 1);}
};