Leetcode(105)

这个题我看到网上有一个很优美的解法，是利用static variable来做的，因为preorder的第一个元素一定是子树的根，同时，下一个元素一定是左子树的根。以此类推。接下来我们在inorder中寻找这个元素对应的位置，那么从start到这个点是左子树，从这个点到end是右子树。这是一个递归的方法。

这个做法非常好，唯一而且是致命的缺点是static变量只能初始化一次，所以这个函数只能运行一次。很尴尬。正确答案如下：

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}

TreeNode* create(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie){
    if(ps > pe){
        return nullptr;
    }
    TreeNode* node = new TreeNode(preorder[ps]);
    int pos;
    for(int i = is; i <= ie; i++){
        if(inorder[i] == node->val){
            pos = i;
            break;
        }
    }
    node->left = create(preorder, inorder, ps + 1, ps + pos - is, is, pos - 1);
    node->right = create(preorder, inorder, pe - ie + pos + 1, pe, pos + 1, ie);
    return node;
}

Let me explain the coordinates in the recursion. Very simply, we can see that the inorder traversal is divided into two parts, [is, pos-1] and [pos+1, ie] according to the root node pointed by pos.The first part contains pos – is elements, and the second part has ie- (pos +1)+1 = ie – pos elements.
Correspondingly, in preorder traversal, the elements in the [ps+1, ps+pos – is] intervals belong to the left subtree, and the elements in the [pe – (ie – pos)+1, pe] interval belong to the right subtree.