题目描述

返回与给定的前序和后序遍历匹配的任何一个二叉树。

pre 和 post 遍历中的值是不同的正整数。

样例

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

注意

• 1 <= pre.length == post.length <= 30
• pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列。
• 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

算法

(栈) $O(n)$

1. 如果仅知道二叉树的前序和后序遍历，是无法唯一确定一个二叉树的，很容易能举出例子。
2. 我们可以沿着前序遍历，用试错的方法来构造这棵二叉树，首先创建一个栈，记录当前结点到根结点的路径。
3. 初始时，建立根结点，栈中存放根结点。
4. 然后找前序遍历的下一个值，如果当前栈顶结点的左右儿子都已经创建了，或者这个值在后序遍历中的位置，大于当前栈顶的值在后序遍历中的位置，则说明新的结点不能作为栈顶结点的子结点，而且根据前序遍历的定义，栈顶结点永远不会再安放新的儿子结点，故栈顶出栈，寻找下一个栈顶。
5. 如果这个值在后序遍历中的位置，小于当前栈顶的值在后序遍历中的位置，则说明后序遍历中，一定是先访问了栈顶的子结点，则可以将新结点放到栈顶结点左儿子或者右儿子（如果左儿子已经创建了）。新结点进栈。
6. 如此循环直到所有结点都创建完毕。

时间复杂度

• 每个结点最多进栈一次，出栈一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要栈，以及一个记录位置的数组，故空间复杂度为 $O(n)$。

C++ 代码

/**
 * 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 n = pre.size();
        vector<int> order(n + 1);
        for (int i = 0; i < n; i++)
            order[post[i]] = i;

        TreeNode *root = new TreeNode(pre[0]);
        stack<TreeNode*> st;
        st.push(root);

        for (int i = 1; i < n; i++) {
            while (!st.empty()) {
                TreeNode* top = st.top();
                if (order[top -> val] < order[pre[i]]
                 || top -> left != nullptr && top -> right != nullptr) {
                    st.pop();
                    continue;
                }
                if (top -> left == nullptr) {
                    top -> left = new TreeNode(pre[i]);
                    st.push(top -> left);
                    break;
                }
                if (top -> right == nullptr) {
                    top -> right = new TreeNode(pre[i]);
                    st.push(top -> right);
                    break;
                }
            }
        }

        return root;
    }
};