这题有意思。一开始还想不清楚，看了解释，很棒。
这个题目的特殊之处是所有节点的值都是不一样的. 所以递归过程可以大大简化. 先看两种遍历的性质:
pre-order: root, left *************, right #########
post-order: **************left, ########right, root
所以 pre-order 的第一个元素一定等于 post-order 的最后一个元素. 然后在post-order中由前往后找, 找出等于pre-oder中第二个元素的位置, 也就是 left 的位置. 如果post-order中的这个位置不是倒数第二个, 说明左右子树都非空, 那么对左右子树递归调用后用乘法原理. 如果是倒数第二个, 说明有一个子树为空, return的值就是 2*递归调用非空子树.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
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);
} |