文章目录

原题

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];
    }
};

复杂度分析

Time Complexity: O(n)
Space Complexity: O(n)


原题:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/
Github 源码:
递归 & 分治策略
参考:
递归公式主定理:https://blog.csdn.net/ycf74514/article/details/48813289
算法分析渐进符号:https://blog.csdn.net/gaoxiangnumber1/article/details/45066841
文章来源:胡小旭 => [LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.