Construct Binary Tree From Inorder And Postorder Traversal

106. 从中序和后序遍历序列构造二叉树

分析

构建哈希表：
- 遍历 inorder 数组，用哈希表记录每个节点值的位置。
- 这样可以快速查找某个节点在中序遍历中的索引。
递归划分左右子树：
- 后序遍历的最后一个元素是根节点。
- 在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
递归构造树：
- 通过子数组的范围递归构造左右子树。
- 递归的边界条件是子数组范围为空。
返回结果：
- 最终返回根节点，即整棵树的构造结果

时间复杂度

构造哈希表需要 O(n)
每次递归通过哈希表查找根节点位置是 O(1)，递归调用总次数为 n，因此递归部分的时间复杂度为 O(n)

总时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 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


class Solution
{
public:
    std::unordered_map<int, int> hash; // 记录中序遍历中每个节点值的位置

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        // 构建哈希表，快速查找中序遍历中每个节点的位置
        for (int i = 0; i < inorder.size(); ++i)
            hash[inorder[i]] = i;

        // 调用递归函数构造二叉树
        return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }

    TreeNode* build(std::vector<int>& inorder, std::vector<int>& postorder, int il, int ir, int pl, int pr)
    {
        // 如果子树范围为空，返回空节点
        if (il > ir)
            return nullptr;

        // 获取当前子树的根节点
        TreeNode* root = new TreeNode(postorder[pr]);
        int mid = hash[root->val]; // 在中序遍历中找到根节点的位置

        // 递归构造左子树
        root->left = build(inorder, postorder, il, mid - 1, pl, pl + mid - 1 - il);

        // 递归构造右子树
        root->right = build(inorder, postorder, mid + 1, ir, pl + mid - 1 - il + 1, pr - 1);

        return root;
    }
};