题目描述

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, ..., pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

题意：从二叉树的前序遍历和后序遍历还原二叉树，如果有多种可能的话，返回其中任意一种。

算法1

(递归) $O(n^2)$

题解：首先从二叉树的前序遍历和后序遍历是没有办法还原唯一一棵二叉树的。考虑先序遍历的顺序：根节点、左子树、右子树；后序遍历的顺序：左子树、右节点、根节点。

为了方便叙述，这里假设下标从1开始。所以对于任何一个子树的遍历，必然有$pre[1] =post[len]$。接下来如果能够确定$pre[2:len]$中哪一部分是左子树，哪一部分是右子树的话，我们就可以递归建立子树了。考虑$pre[2]$，他在左子树的先序遍历是第一个出现的，那么意味着他在左子树的后序遍历中是最后一个出现的。因此，我们只需要找到$post$数组中等于$pre[2]$的元素$post[i]$，那么$post[1:i]$中的元素就是左子树的元素啦。

因为这题确保有正确的解，否则我们还需要判断这两段区间包含的元素是否完全相同。

C++ 代码

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return construct(pre,0,pre.size() - 1,post,0,pre.size() - 1);
    }
    //  pre_b,pre_e,post_b,post_e分别代表当前树的先序遍历和后序遍历的元素的区间范围
    //  如果区间长度小于等于0，返回NULL，如果区间长度等于1，返回该节点。
    //  如果大于1，找到其左子树和右子树的分界点，递归建立左子树和右子树
    TreeNode* construct(vector<int>& pre,int pre_b,int pre_e,vector<int>& post,int post_b,int post_e)
    {
        if(pre_b > pre_e) return NULL;
        TreeNode* root = new TreeNode(pre[pre_b]);
        if(pre_b == pre_e)
            return root;
        for(int i = post_b ; i < post_e ; i ++)
        {
            if(post[i] == pre[pre_b + 1])
            {
                root->left = construct(pre,pre_b + 1,pre_b + i - post_b + 1,post,post_b,i);
                root->right = construct(pre,pre_b + i - post_b + 2,pre_e,post,i + 1,post_e - 1);
                break;
            }
        }
        return root;
    }
};