leetcode105

/**
 * 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 = 0;
        return createBST(preorder,inorder,root_index,preorder.size()-1,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-1 >= start)
            root->left = createBST(preorder,inorder,start,i-1,++index);
        if (end >= i+1)
            root->right = createBST(preorder,inorder,i+1,end,++index);
        return root;
    }
};

这是一道分治的题目，用先序找到根节点，用中序找到其左右子树。

补充一个我认为比较容易理解的版本，使用python 实现：

 1 class Solution:
 2     def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
 3         if len(preorder)==0 or len(inorder)==0:
 4             return None
 5 
 6         val = preorder[0]
 7         t = TreeNode(val)
 8         index = inorder.index(val)
 9         t.left = self.buildTree(preorder[1:index+1],inorder[:index])
10         t.right = self.buildTree(preorder[index+1:],inorder[index+1:])
11         return t