Skip to content

Latest commit

 

History

History
160 lines (112 loc) · 6.1 KB

面试题7_重建二叉树.md

File metadata and controls

160 lines (112 loc) · 6.1 KB
Raw

面试题 7：重建二叉树

leetcode-cn 题目地址

📗difficulty：Medium

🎯Tags：

1. 题目描述📃

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

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

例如，给出

  • 前序遍历 preorder = [3,9,20,15,7]
  • 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

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

2. 解题思路💡

在二叉树的先序遍历中，第一个数字总是树的根节点的值。

但是在中序遍历的序列中，根节点的值在序列的中间，而且左子树的节点的值位于根节点的左边，右子树的节点的值位于根节点的右边。而题目描述中有“保证全部的节点值不重复”，遍历一次中序遍历的序列，就能找到根节点的值在中序遍历序列中的位置。

对于下面的这个树：

  • 先序遍历序列：{1, 2, 4, 7, 3, 5, 6, 8}
  • 中序遍历序列：{4, 7, 2, 1, 5, 3, 8, 6}

可以根据上述分析，得到下面这个结论：

那么获得了左子树和右子树之后，可以用同样的方法来构建左子树的左、右子树，即使用递归的思想来完成。

对于递归，关键在于找出其递归终止的条件。

对于本题来说，有以下 2 个终止的条件：

  • 当 start 指针大于 end 指针时，意味着没有节点，返回 null
  • 当 start 指针等于 end 指针时，有且只有根节点 ，返回该节点

其他情况，则说明有左子树和右子树的情况，继续递归处理即可。

根据上述逻辑，可以编写以下代码：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0) {
        return null;
    }
    Map<Integer, Integer> indexMap = new HashMap<>();
    int length = preorder.length; // 树中的节点数量与遍历方式无关
    for (int i = 0; i < length; i++) {
        indexMap.put(inorder[i], i);
    }
    TreeNode root = buildTree(preorder, 0, length - 1,
                              inorder, 0, length - 1,
                              indexMap);
    return root;
}

public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd,
                          int[] inorder, int inorderStart, int inorderEnd,
                          Map<Integer, Integer> indexMap) {
    if (preorderStart > preorderEnd) {
        // 递归结束情形 1 : 先序遍历的开始范围大于结束范围，此时表示二叉树中没有节点
        return null;
    }

    int rootVal = preorder[preorderStart]; // 先序遍历的情况下，第一个 index 处为根节点
    TreeNode root = new TreeNode(rootVal);
    if (preorderStart == preorderEnd) {
        // 递归结束情形 2 : 开始等于结束，意味着当前二叉树中只有一个节点，以该节点值创建根节点并返回
        return root;
    } else {
        int rootIndex = indexMap.get(rootVal);
        int leftNodes = rootIndex - inorderStart;
        int rightNodes = inorderEnd - rootIndex;
        // 左右子树的构建
        // 注意先序和中序的下标位置
        TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes,
                                         inorder, inorderStart, rootIndex - 1,
                                         indexMap);
        TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd,
                                          inorder, rootIndex + 1, inorderEnd,
                                          indexMap);
        root.left = leftSubtree;
        root.right = rightSubtree;
        return root;
    }
}

上述代码逻辑来自于 leetcode-cn 官方题解。

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

简化版本

上述代码的代码有些冗长，但其思路较为清晰，配合图示已于理解。

下述代码更加简洁，更加显示了递归解法的简洁性。

class Solution {
    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] po;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++) 
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}

复杂度分析

  • 时间复杂度：

    • O(N) 。N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) ；递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此递归占用 O(N) 。（最差情况为所有子树只有左节点，树退化为链表，此时递归深度 O(N) ；平均情况下递归深度平均情况下递归深度 O(log2 N)）。

  • 空间复杂度：O(N) 。HashMap 使用 O(N) 额外空间；递归操作中系统需使用 O(N) 额外空间。

3. 总结🎯

对于树的题目，很多时候重点考察对递归的理解和熟练掌握的程度。

树的知识中，很重要的一个部分是树的遍历，其中又考察到对递归的理解。树的遍历有很强的规律性，即特点。例如在本题中，先序遍历的第一个节点为根节点，这个特性被用于解题，如果对树的遍历的特点掌握不好，难以解出此题。