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

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

内容简介：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];
    }
};