剑指 Offer 07. 重建二叉树

本问题对应的 leetcode 原文链接:剑指 Offer 07. 重建二叉树
本次对应打卡问题:【二叉树专题】剑指 Offer 07. 重建二叉树

问题描述

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

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

示例 1:

07

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

解题思路

视频讲解直达: 本题视频讲解

代码实现

    Map< Integer, Integer > map = 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++) {
            map.put(inorder[i], i);
        }

        TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

        return root;
    }

    TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        // 前序遍历或者中序遍历为空时,表示这棵树不存在,直接返回 null
        if( l1 > r1 || l2 > r2){
            return null;
        }
        // 根节点
        TreeNode root = new TreeNode(preorder[l1]);
        // 根节点在中序遍历中的下标
        int i = map.get(preorder[l1]);
        // 递归求解
        root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i - 1);
        root.right = f(preorder, l1 + (i - l2) + 1, r1, inorder, i + 1, r2);

        return root;
    }

  • 时间复杂度 O(N) : 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ,占用 O(N) 。递归共建立 NN 个节点,每层递归中的节点建立、搜索操作占用 O(1) ,因此使用 O(N) 时间。
  • 空间复杂度 O(N) : HashMap 使用 O(N) 额外空间;最差情况下(输入二叉树为链表时),递归深度达到 N ,占用 O(N)的栈帧空间;因此总共使用 O(N) 空间。

发表回复

后才能评论