LeetCode 889. 根据前序和后序遍历构造二叉树

一、题目

1、题目描述

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

2、接口描述

​

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {

    }
};

3、原题链接

889. 根据前序和后序遍历构造二叉树

二、解题报告

1、思路分析

前序遍历：根-左-右

后序遍历：左-右-根

我们哈希预处理后序序列值根下标的映射

然后根据前序遍历找到左子树（因为不构造结果不唯一，直接当成左子树就行）的根，从而在后序遍历中划分出左右子树，继而递归

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

​

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
int mp[35];
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++) mp[postorder[i]] = i;
        function<TreeNode*(int, int, int, int)> dfs = [&](int st1, int ed1, int st2, int ed2) -> TreeNode*{
            if(st1 > ed1) return nullptr;
            TreeNode* ret = new TreeNode(preorder[st1]);
            if(st1 != ed1){
                int p = mp[preorder[st1 + 1]], len = p - st2 + 1;
                ret->left = dfs(st1+1, st1+len, st2, p),
                ret->right = dfs(st1+len+1, ed1, p+1, ed2-1);
            }
            return ret;
        };
        return dfs(0, n - 1, 0, n - 1);
    }
};