Construct Binary Tree from Preorder and Postorder Traversal

题目

Construct Binary Tree from Preorder and Postorder Traversal
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.

解题报告

理解题意

• 给定两个数组，分别表示先序遍历和后序遍历
• 要求根据两个遍历结果构造出原来的二叉树

思路

递归解法

• 创建一个节点 TreeNode[pre[preIndex]] 作为根节点
• 由于后序遍历中根节点是最后访问的，因此构造结束的条件就是：root->val == post[postIndex]
• 那么，如果还没有创建完二叉树，我们就递归的对于左子树和右子树调用构造函数。

class Solution {
private:
    int preIndex = 0;
    int postIndex = 0;
public:
    TreeNode *constructFromPrePost(vector<int>& pre, vector<int>& post) {
        TreeNode *root = new TreeNode(pre[preIndex++]);
        if (root->val != post[postIndex])
            root->left = constructFromPrePost(pre, post);
        if (root->val != post[postIndex]) {
            root->right = constructFromPrePost(pre, post);
        }
        postIndex++;
        return root;
    }
};

非递归解法

• 使用栈，前序生成二叉树，将生成的结果 push 到 stack 中，然后使用后续 pop 出来
• stack 保存的是当前的树
• node == new TreeNode(pre[i]) ，如果没有左子节点，就把它作为左子节点，否则就是右子节点。
• 如果在前序遍历和后序遍历碰到了相同的值，那么就说明当前子树构造结束，将其 pop 出来

class Solution {
public:
    TreeNode * constructFromPrePost(vector<int>&pre, vector<int> &post) {
        vector<TreeNode*> stk_;
        stk_.push_back(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.size(); i++) {
            TreeNode *node = new TreeNode(pre[i]);
            while (stk_.back()->val == post[j]) {
                stk_.pop_back();
                j++;
            }
            if (stk_.back()->left == nullptr) {
                stk_.back()->left = node;
            } else {
                stk_.back()->right = node;
            }
            stk_.push_back(node);
        }
        return stk_[0];
    }
};

时间复杂度

遍历次数：O(n)，因此是线性时间，每个元素只遍历一次

空间复杂度

O(n) 表示栈的大小