这题有意思。一开始还想不清楚，看了解释，很棒。
这个题目的特殊之处是所有节点的值都是不一样的. 所以递归过程可以大大简化. 先看两种遍历的性质:
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);} |
原文：http://www.cnblogs.com/lautsie/p/3528926.html