/**
* 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) {
if (preorder.empty())
return NULL;
int root_index = ;
return createBST(preorder,inorder,root_index,preorder.size()-,root_index);
}
TreeNode* createBST(vector<int>& preorder, vector<int>& inorder, int start, int end, int& index) {
int v = preorder[index];
int i = start;
for (i; i <= end; i++)
if (v == inorder[i])
break;
TreeNode* root = new TreeNode(v);
if (i- >= start)
root->left = createBST(preorder,inorder,start,i-,++index);
if (end >= i+)
root->right = createBST(preorder,inorder,i+,end,++index);
return root;
}
};
这是一道分治的题目，用先序找到根节点，用中序找到其左右子树。
补充一个我认为比较容易理解的版本，使用python 实现：
class Solution:
def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
if len(preorder)== or len(inorder)==:
return None val = preorder[]
t = TreeNode(val)
index = inorder.index(val)
t.left = self.buildTree(preorder[:index+],inorder[:index])
t.right = self.buildTree(preorder[index+:],inorder[index+:])
return t