[LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。