剑指 Offer 07. 重建二叉树

title: 剑指 Offer 07. 重建二叉树 tags:

二叉树
递归 categories:
算法
剑指 Offer

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

$0 <= 节点个数 <= 5000$

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

算法

(递归)) $O(n)$

由数据结构的知识可知根据二叉树的前序遍历和中序遍历可以唯一确定一棵二叉树。

首先定义一个哈希表 $pos$，存储中序序列中每个元素出现的位置，用于前序序列中的元素定位在中序序列中的位置，前序序列的遍历顺序是 根左右，那么第一个元素就是整棵树的根节点，而中序序列的遍历顺序是 左根右，通过哈希表 $pos$ 可以知道根节点在中序序列中的位置，同时确定左子树和右子树的范围，从而确定在前序序列中左子树和右子树的范围。同样的逻辑，递归的处理下去，就可以得到二叉树的结构。

算法步骤：

预处理中序序列中每个元素出现的位置，存到哈希表中
由前序序列得到根节点的值，创建根节点，定位根节点在中序序列中的位置，确定左右子树的范围。
递归处理左子树
递归处理右子树

时间复杂度

每次递归会创建一个节点，总共 $n$ 个节点，所以总时间复杂度为 $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:
    unordered_map<int, int> pos;

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        int k = pos[preorder[pl]];
        auto root = new TreeNode(inorder[k]);
        root->left = build(preorder, inorder, pl + 1, pl + k - il, il, k - 1);
        root->right = build(preorder, inorder, pl + k - il + 1, pr, k + 1, ir);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        for (int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i;
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, Integer> pos = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        for (int i = 0; i < inorder.length; i ++ ) {
            pos.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) {
            return null;
        }
        int k = pos.get(preorder[pl]);
        TreeNode root = new TreeNode(inorder[k]);
        root.left = build(preorder, inorder, pl + 1, pl + k - il, il, k - 1);
        root.right = build(preorder, inorder, pl + k - il + 1, pr, k + 1, ir);
        return root;
    }
}

Python 代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        pos = {val: idx for idx, val in enumerate(inorder)}

        def build(pl, pr, il, ir):
            if pl > pr:
                return None
            k = pos[preorder[pl]]
            root = TreeNode(inorder[k])
            root.left = build(pl + 1, pl + k - il, il, k - 1)
            root.right = build(pl + k - il + 1, pr, k + 1, ir)
            return root

        if not preorder:
            return None
        return build(0, len(preorder) - 1, 0, len(inorder) - 1)