文章目录

原题

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.

题解

考察构造二叉树，其需要同时满足输入的先序遍历和后序遍历。并输出任意一个满足要求的解。为什么说要输出任意一个满足的解，因为在这种情况下，会有两种解：

pre = [1, 2, 4]
post = [4, 2, 1]

第一种情况

    1
  2
4

第二种情况

    1
  2
    4

以上两种情况都是满足原题要求的，所以当一个节点只有一个子节点时，默认地认为它是该节点的左子节点，即第一种情况的解。

递归 & 分治策略

pre (root)  (left)  (right)
     1,      2,4,5,  3,6,7
post (left)  (right)  (root)
      4,5,2,  6,7,3,   1

分析原题的pre和post向量可知，pre[0]是root，假设map m。m->first代表每一个节点的值（val），m->second代表其所属的索引。则可知道post[pre[1]] + 1就是当前root的左节点的所有元素个数（长度）。同理，可以容易推出右节点的所有元素的个数。
那么利用分治策略，将一个大规模的问题分解成两个更小规模的问题，不断的递归下去，直到逼近边界条件，当可以容易求出解时返回。

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post)
    {
        int len = post.size();
        // traversing the post
        for (int i = 0; i < len; i++)
        {
            m[post[i]] = i;
        }
        return construct(pre, post, 0, len – 1, 0, len – 1);
    }

    TreeNode *construct(vector<int> &pre, vector<int> &post, int pre_s, int pre_e, int post_s, int post_e)
    {
        // boundary conditions
        if (pre_s > pre_e)
            return nullptr;
        TreeNode *root = new TreeNode(pre[pre_s]);
        if (pre_s == pre_e)
            return root;

        // get left & right node
        int left_len = m[pre[pre_s + 1]] – post_s + 1;
        root->left = construct(pre, post, pre_s + 1, pre_s + left_len, post_s, post_s + left_len – 1);
        root->right = construct(pre, post, pre_s + left_len + 1, pre_e, post_s + left_len, post_e – 1);

        return root;
    }

private:
    map<int, int> m;
};

复杂度分析

Time Complexity: O(n) ~ O(n^2)
当树是一个理想状态（满二叉树）时，他的递归深度f(n) = log(n+1)/2 = O(logn)，此时递归公式为：T(n) = aT(n/b) + O(1) = 2T(n/2) + O(1)，根据主定理可知，T(n) = O(n)
当树是一个最差状态时，即每个节点最多只有一个做节点，他的递归深度f(n) = O(n)
Space Complexity: O(logn) ~ O(n)

*迭代 & stack

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
    TreeNode *constructFromPrePost(vector<int> pre, vector<int> post)
    {
        vector<TreeNode *> s;
        s.push_back(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.size(); ++i)
        {
            TreeNode *node = new TreeNode(pre[i]);
            while (s.back()->val == post[j])
                s.pop_back(), j++;
            if (s.back()->left == NULL)
                s.back()->left = node;
            else
                s.back()->right = node;
            s.push_back(node);
        }
        return s[0];
    }
};