算法题006：根据前序和后序遍历构造二叉树

发表于 分类于 本文字数： 923 阅读时长 ≈ 3 分钟

题目

题目来源：889. 根据前序和后序遍历构造二叉树（每日一题）

题目描述：

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

img

1
2
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

1
2
输入: preorder = [1], postorder = [1]
输出: [1]

提示：

  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • preorder 中所有值都 不同
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • postorder 中所有值都 不同
  • 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

思路

首先，前序和后序构造的二叉树不唯一，因此不存在确定的规则，自由反而带来了坏处。与之相对的，『中序和前序』以及『中序和后序』只对应唯一的二叉树，规则明确，按照规则写代码即可。因此，我们要自定义规则。

回忆用『中序和前序』构造二叉树，我们顺序遍历前序列表，每遍历一个值，创建对应节点，然后根据中序确定其子树。这可以理解为前序创建，中序校验。

同理，在这道题中，我们也是“顺序遍历前序列表，每遍历一个值，创建对应节点”，但是根据后序确定 该节点的位置 （而不是其子树）—— 前序创建，后序校验。

前序是“中左右”，每遍历前序列表一个节点，我们都可以尝试把它放到左子节点。而后序是“左右中”，假设在后序列表中节点 A 在 B 之后，那么 A 绝对不可能在 B 的左子树中。

例如，观察示例 1 的节点 5。顺序遍历前序列表，我们尝试把 5 作为 4 的左子节点。但是在后序列表中，5 在 4 之后，那么这种尝试是不允许的。 5 只可能在 4 的某一个祖先的右子树中，在这里是 2 的右节点。

因此，我们需要追踪从根节点到上一个遍历到的节点的一条路径，将它们存入一个栈中。

  • 只要当前节点和栈顶节点不满足上述后序约束，就出栈，直到满足为止。此时，当前节点是栈顶节点的右子节点。
  • 如果已经满足约束，当前节点直接成为栈顶节点的左子节点。

代码

上述思路是一个大致描述，还是要注意一些细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n = preorder.size();
        // 只操作 vector 尾部，相当于 stack
        vector<TreeNode*> ve;
        unordered_map<int, int> mp;
        // 和『中序和前序』一样，将校验列表的 <元素, 索引> 存入哈希表
        for (int i = 0; i < n; ++i) {
            mp[postorder[i]] = i;
        }
        for (int v: preorder) {
            TreeNode* cur = new TreeNode(v);
            // 只有第一个元素（根节点）才可能触发这个条件
            if (ve.empty()) {
                ve.push_back(cur);
                continue;
            }
            bool popped = false;
            while((!ve.empty()) && (mp[v] > mp[ve.back()->val])) {
                ve.pop_back();
                popped = true;
            }
            if (!popped) {
                ve.back()->left = cur;
            } else {
                ve.back()->right = cur;
            }
            // 存入当前节点，用于下一个节点的判断
            ve.push_back(cur);
        }
        // 第一个节点永远是根节点，且不会被弹出
        return ve.front();
    }
};

时间复杂度：$O(n)$

  • 顺序遍历 preorder 和 postorder；
  • 所有节点只会进出 ve 一次；

空间复杂度：$O(n)$

  • mp 存放了 $n$ 个节点的值及其索引；
  • 最坏的情况，所有节点都进入 ve；