# C++ 40ms, solved recursively

• 递归实现。

1. 先找到根节点

2. 分别找到：左子树的前序遍历和中序遍历，右子树的前序遍历和中序遍历

3. 分别对“左子树的前序遍历和中序遍历”和“右子树的前序遍历和中序遍历”递归调用buidTree函数(private)
得到左子树和右子树的根节点

4. 将根节点与左子树和右子树连起来

class Solution
{
public:
TreeNode buildTree(vector<int> &preorder, vector<int> &inorder)
{
int preSize = preorder.size();
int inSize = inorder.size();
/

if(preSize!=inSize)
throw;
if(preSize==0)
return NULL;

``````     if(preSize!=inSize)
throw;
*/
TreeNode *root = buildTree(preorder,0,preSize,inorder,0,inSize);

}
``````

private:
TreeNode *buildTree(vector<int> &preorder,int preorderL,int preorderR,
vector<int> &inorder, int inorderL,int inorderR)
{
//base line
int preSize = preorderR-preorderL;
int inSize = inorderR-inorderL;
if(preSize!=inSize)
throw;
if(preSize==0)
return NULL;

``````     int root_val = preorder[preorderL];
TreeNode *root = new TreeNode(root_val);

if(preSize==1)
return root;

//利用根节点的数值找出左子树和右子树的范围
int index = 0;
for(;inorder[index+inorderL]!=root_val && index+inorderL<inorderR;++index)
{}
if(index>=inorderR)
throw;

//左子树前序遍历和中序遍历的范围
int leftSubtreePreorderL = preorderL+1;
int leftSubtreePreorderR = preorderL+index+1;
int leftSubtreeInorderL = inorderL;
int leftSubtreeInorderR = inorderL + index;
``````
``````        //右子树前序遍历和中序遍历的范围
int rightSubtreePreorderL = preorderL+index+1;
int rightSubtreePreorderR = preorderR;
int rightSubtreeInorderL = inorderL+index+1;
int rightSubtreeInorderR = inorderR;

//递归调用
TreeNode *leftSubtree = buildTree(preorder,leftSubtreePreorderL,leftSubtreePreorderR,
inorder,leftSubtreeInorderL,leftSubtreeInorderR);
TreeNode *rightSubtree = buildTree(preorder,rightSubtreePreorderL,rightSubtreePreorderR,
inorder,rightSubtreeInorderL,rightSubtreeInorderR);

root->left = leftSubtree;
root->right = rightSubtree;

return root;
}
};``````

• ``````struct TreeNode *buildTree(int *preorder, int *inorder, int n) {
if(n == 0)
return NULL;

struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = preorder[0];

int rootIndex;
for(rootIndex=0; inorder[rootIndex] != root->val; ++rootIndex);

root->left = rootIndex == 0 ? NULL : buildTree(preorder+1, inorder, rootIndex);

root->right = rootIndex == n-1 ? NULL : buildTree(preorder+rootIndex+1, inorder+rootIndex+1, n-rootIndex-1);

return root;
}``````

• Your code is more succinct. You must be more familiar with c/c++ than I.

• 递归不用这么麻烦吧............

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.