LeetCode第 889 题：根据前序和后序遍历构造二叉树 (C++)_根据前序和后序遍历构建二叉树c

889. 根据前序和后序遍历构造二叉树 - 力扣（LeetCode）

系列题：
LeetCode第 105 题：从前序与中序遍历序列构造二叉树 (C++)_zj-CSDN博客
LeetCode第 106 题：从中序与后序遍历序列构造二叉树 (C++)_zj-CSDN博客

但是这一题有一点不一样，因为根据前序遍历和后续遍历并不能唯一确定一棵树：

以上两种情况就区分不开：当一结点只有一个孩子时，无论他是左孩子还是右孩子，他们的前序遍历与后序遍历结果都是一样。

不过本题仅仅要求随意返回一颗就可以了。

前序遍历：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

后续遍历：

[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点]

首先前序遍历的第二个点可能是左子树根或者右子树根，后续遍历倒数第二个节点也可能是左子树根或者右子树根：

• 如果这两个位置数值不同，那么前序第二个点是左子树根，后续倒数第二个点是右子树根
• 如果数值相同则既有可能是左子树又有可能是右子树，判定为多解；放到左右子树都可以

解法和之前的类似：

class Solution {
public:
    unordered_map<int, int> m;
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        for(int i = 0; i < post.size(); ++i)    m[post[i]] = i;
        return help(pre, 0, pre.size()-1, 0, post.size()-1);   
    }
    TreeNode* help(vector<int>& pre, int l1, int r1, int l2, int r2){
        if(r1 < l1 || r2 < l2) return NULL;
        auto root = new TreeNode(pre[l1]);
        if(l1 == r1)    return root;//这儿一定要有
        //这儿是pre[l1+1]，也就是前序根节点的下一个节点
        int idx = m[pre[l1+1]], len = idx - l2 + 1;
        root->left = help(pre, l1+1, l1+len, l2, idx);
        root->right = help(pre, l1+len+1, r1, idx+1, r2-1);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

关于这一题的一个扩展，如果问题改为：给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

SOJ 1210 二叉树 - KennyRom - 博客园

首先，二叉树的前序遍历结果与后序遍历结果，是无法确定唯一的二叉树的。

当一结点只有一个孩子时，无论他是左孩子还是右孩子，他们的前序遍历与后序遍历结果都是一样的。这就是无法唯一确定的原因，一棵树中有多少个这种情况，就会有2^多少种中序遍历结果。

已知先序后序遍历找n种二叉树问题_wyxwyx469410930的博客-CSDN博客
思路：
①设共有n个结点;(设二叉树先序遍历序列为A[n],后序遍历序列为B[n])
②遍历二叉树先序遍历，从第i(i>=2)个开始，使用find函数找到后序遍历B[i]中A[i]的位置x
③比较A[i] == B[x] && A[i+1] == B x - 1 是否成立
③如果成立则证明先序遍历第i+1个位置是一个单叶节点，也即二叉树的情况多了2倍

#include <iostream>
#include <string>
using namespace::std;
int main() {
    string pre, post;
    cin >> pre >> post;
    int cnt = 1;
    for (int i = 0; i < pre.size()-1-1; ++i) {
        int j = post.find(pre[i]);
        if (j < 1) continue;//无法访问j-1
        if (pre[i + 1] == post[j - 1])
            cnt *= 2;
    }
    cout << cnt;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16