LeetCode889. Construct Binary Tree from Preorder and Postorder Traversal（二叉树 / 思维）

Medium
Accepted：12,148
Submissions：20,848

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.

链接

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

题意

给定一个二叉树的前序遍历和后序遍历，构造这棵二叉树，答案不唯一，输出一个即可。

题解

之前我们在LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal（二叉树 / 思维）讲了如何通过前序遍历和中序遍历唯一确定一棵二叉树，实际上前序遍历和后序遍历的做法是类似的，都是首先找根节点然后确定左右子树最后递归处理。

pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]

[1] 2 4 5 3 6 7 // 1为根节点
4 5 2 6 7 3 [1]

[1] [2] 4 5 3 6 7 // 2为根节点，找到2在后序遍历中的位置
4 5 [2] 6 7 3 [1] // 其中[4, 5, 2]就是1的左子树，[6, 7, 3]为1的右子树

然后对左右子树[2, 4, 5] & [4, 5, 2] [3, 6, 7] & [6, 7, 3]做递归处理

实际上就是对于先序遍历我们第一个结点为根结点root，然后我们把根结点右边的第一个结点rootLeft作为它左子树的根结点，确定rootLeft在后续遍历中的位置，就可以确定左右子树了。

当然平均时间复杂度依然是$O(n^2)$。

代码

Runtime: 16 ms, faster than 85.47% of C++ online submissions for Construct Binary Tree from Preorder and Postorder Traversal.
Memory Usage: 14.7 MB, less than 24.14% of C++ online submissions for Construct Binary Tree from Preorder and Postorder Traversal.

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        int n = pre.size();
        return solve(pre, post, 0, 0, n);
    }

private:
    TreeNode* solve(vector<int>& pre, vector<int>& post, int preStart, int postStart, int size)
    {
        if (size <= 0)
            return NULL;
        if (size == 1) // 注意一个结点的情况
        {
            TreeNode* bt = new TreeNode(pre[preStart]);
            bt->left == NULL;
            bt->right == NULL;
            return bt;
        }
        TreeNode* bt = new TreeNode(pre[preStart]);
        int root = pre[preStart+1], pos = 0; // pos代表根节点在后序遍历中位置，默认为0
        for (int i = postStart; i < postStart + size; ++i)
        {
            if (post[i] == root)
            {
                pos = i;
                break;
            }
        }
        pos = (pos == 0) ? pos : pos - postStart; // 之前是从postStart的所以要减去
        bt->left = solve(pre, post, preStart + 1, postStart, pos + 1);
        bt->right = solve(pre, post, preStart + pos + 2, postStart + pos + 1,  size - pos - 2);
        return bt;
    }
};

因为我们每次都是找根结点的右一结点的位置，所以要考虑只有一个结点的情况。

The end.
2019年3月14日星期四