# [ItInt5] Number of Valid Trees Given Preorder and Postorder

### Question

Example

``````前序遍历序列preorder：1 2

1       1
/         \
2           2
``````

### Solution

pre-order: root, left *************, right #########

post-order: **************left, ########right, root

1. 如果 p 位置不是倒数第二个, fine, 对左右子树递归调用后用乘法原理.

2. 如果 p 是倒数第二个, 说明either left branch or right branch为空, return的值就是 2 * 递归调用非空子树.

ref

### Code

not written by me. This code is REALLY 叼炸天。

``````int helper(vector<int>& preorder, vector<int>& posorder,
int i1, int j1, int i2, int j2){
if(i1 == j1) return 1;
if(preorder[i1+1] == posorder[j2-1]){
return 2*helper(preorder, posorder, i1+1, j1, i2, j2-1);
}
int k = i2;
while(posorder[k] != preorder[i1+1]){ k++; }
return helper(preorder, posorder, i1+1,i1+1+k-i2 ,i2 , k)
* helper(preorder, posorder, i1+2+k-i2, j1, k+1, j2-1);
}

int countValidTrees(vector<int>& preorder, vector<int>& posorder) {
int n = preorder.size();
return helper(preorder, posorder, 0, n-1, 0, n-1);
}
``````