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

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