剑指 Offer 07. 重建二叉树 #

问题描述#

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7
限制：

0 <= 节点个数 <= 5000

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

解题思路#

preorder 中的每个值都作为新的根结点，在 inorder 中，该值的位置确定了左右子树的界限。

\(\text{preorder} = [\boxed{3},9,20,15,7], \text{inorder}=[\underbrace{9}_{左子树},\underbrace{\boxed{3}}_{根结点}, \underbrace{15,20,7}_{右子树}]\)
\(\text{preorder} = [\boxed{9}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{9}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)
\(\text{preorder} = [\boxed{20},15,7], \text{inorder}=[\underbrace{15}_{左子树},\underbrace{\boxed{20}}_{根结点}, \underbrace{7}_{右子树}]\)
\(\text{preorder} = [\boxed{15}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{15}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)
\(\text{preorder} = [\boxed{7}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{7}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)

根据 \(\texttt{preorder}\) 根结点确定 \(\texttt{inorder}\) 中的根结点的位置，进而确定下一步中左右子树的范围以及根结点位置。

在先序遍历中，某个结点的 左子树的根结点 就在该结点之后，而该结点的 右子树的根结点 则在该结点加上 左子树结点数量 之后。

Python

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

        def dfs(preorder_root: int, inorder_left: int, inorder_right: int) -> TreeNode:
            if inorder_left > inorder_right: return None

            root = TreeNode(preorder[preorder_root])
            inorder_root = index[preorder[preorder_root]]

            root.left = dfs(preorder_root + 1, inorder_left, inorder_root - 1)
            root.right = dfs(preorder_root + (inorder_root - inorder_left) + 1, inorder_root + 1, inorder_right)

            return root

        return dfs(0, 0, len(inorder) - 1)

C++

class Solution {
public:
    unordered_map<int, int> index;

    TreeNode* dfs(vector<int> &preorder, vector<int> &inorder, int preorder_root, int inorder_left, int inorder_right) {
        if (inorder_left > inorder_right) return nullptr;

        auto root = new TreeNode(preorder[preorder_root]);
        int inorder_root = index[preorder[preorder_root]];

        root->left = dfs(preorder, inorder, preorder_root + 1, inorder_left, inorder_root - 1);
        // inorder_root - inorder_left 为左子树元素个数
        root->right = dfs(preorder, inorder, preorder_root + (inorder_root - inorder_left) + 1, inorder_root + 1, inorder_right);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();

        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }

        return dfs(preorder, inorder, 0, 0, n - 1);
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

剑指 Offer 07. 重建二叉树#

问题描述#

解题思路#

剑指 Offer 07. 重建二叉树 #