这题有意思。一开始还想不清楚，看了解释，很棒。
这个题目的特殊之处是所有节点的值都是不一样的. 所以递归过程可以大大简化. 先看两种遍历的性质:
pre-order: root, left *************, right #########
post-order: **************left, ########right, root
所以 pre-order 的第一个元素一定等于 post-order 的最后一个元素. 然后在post-order中由前往后找, 找出等于pre-oder中第二个元素的位置, 也就是 left 的位置. 如果post-order中的这个位置不是倒数第二个, 说明左右子树都非空, 那么对左右子树递归调用后用乘法原理. 如果是倒数第二个, 说明有一个子树为空, return的值就是 2*递归调用非空子树.
int countHelper(vector<int>& preorder, vector<int>& postorder, int preA, int preB, int postA, int postB) {
if (preA > preB || postA > postB) return 0;
if (preA == preB && postA == postB && preorder[preA] == postorder[postB]) return 1;
// preB > preA && postB > postA
// assert(preorder[preA] == postorder[postB]
if (preorder[preA+1] == postorder[postB-1]) { // right tree or left tree is null
return 2 * countHelper(preorder, postorder, preA+1, preB, postA, postB-1);
} else { // right tree and left tree both exists
int rightInPreOrder = -1;
for (int i = preA+2; i < preorder.size(); i++) {
if (preorder[i] == postorder[postB-1]) {
rightInPreOrder = i;
break;
}
}
int leftInPostOrder = -1;
for (int i = postB-2; i >= 0; i--) {
if (postorder[i] == preorder[preA+1]) {
leftInPostOrder = i;
break;
}
}
return countHelper(preorder, postorder, preA+1, rightInPreOrder-1, postA, leftInPostOrder) *
countHelper(preorder, postorder, rightInPreOrder, preB, leftInPostOrder+1, postB-1);
}
}
int countValidTrees(vector<int>& preorder, vector<int>& postorder) {
// assert(preorder.size() == postorder.size());
return countHelper(preorder, postorder, 0, preorder.size()-1, 0, postorder.size()-1);
}