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

栏目: 数据库 · 发布时间: 6年前

内容简介:Return any binary tree that matches the given preorder and postorder traversals.Values in the traversals

原题

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]

第一种情况

第二种情况

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

递归 & 分治策略

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web开发敏捷之道

Web开发敏捷之道

Sam Ruby、Dave Thomas、David Heineme Hansson / 慕尼黑Isar工作组、骆古道 / 机械工业出版社 / 2012-3-15 / 59.00元

本书第1版曾荣获Jolt大奖“最佳技术图书”奖。在前3版的内容架构基础上,第4版增加了关于Rails中新特性和最佳实践的内容。本书从逐步创建一个真正的应用程序开始,然后介绍Rails的内置功能。全书分为3部分,第一部分介绍Rails的安装、应用程序验证、Rails框架的体系结构,以及Ruby语言的知识;第二部分用迭代方式创建应用程序,然后依据敏捷开发模式搭建测试案例,最终用Capistrano完成......一起来看看 《Web开发敏捷之道》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换