今日算法04-重建二叉树

一、题目描述

题目链接：https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

难易程度：中等

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

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

二、解题思路

分治法

前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。

中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

根据以上性质，可得出以下推论：

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

解决这类问题适合用分而治之的思想，分治的代码可以归纳为如下结构：

def divide_conquer(problem, param1, param2, ...):
    # 1.终止条件
    if problem is None:
        print_result
        return
    # 2.准备数据
    data = prepare_data(problem)
    subproblems = split_problem(problem, data)
    # 3.处理子问题
    subresult1 = self.divide_conquer(subproblems[0], p1, ...)
    subresult2 = self.divide_conquer(subproblems[1], p1, ...)
    subresult3 = self.divide_conquer(subproblems[1], p1, ...)
    # ...
    
    result = process_result(subresult1, subresult2, subresult3, ...)

分治算法解析：

1. 终止条件：根节点在前序遍历的索引 root 、子树在中序遍历的左边界 preL 、子树在中序遍历的右边界 preR ；当 preL > preR ，代表已经越过叶节点，此时返回 null ；

2. 准备数据：

   • 建立根节点 node：节点值为 preorder[root] ；
   • 划分左右子树：查找根节点在中序遍历 inorder 中的索引 i ；

3. 处理子问题：开启左右子树递归；

   	根节点索引	中序遍历左边界	中序遍历右边界
   左子树	root + 1	left	i - 1
   右子树	i - left + root + 1	i + 1	right

复杂度分析

时间复杂度：O(N) ，其中 N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。

空间复杂度：O(N) ，HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N) 的栈帧空间；因此总共使用 O(N) 空间。

三、代码实现

// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    for (int i = 0; i < in.length; i++)
        indexForInOrders.put(in[i], i);
    return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
}

private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
    if (preL > preR)
        return null;
    TreeNode root = new TreeNode(pre[preL]);
    int inIndex = indexForInOrders.get(root.val);
    int leftTreeSize = inIndex - inL;
    root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
    root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
    return root;
}

推荐阅读

• 二维数组中的查找

封面

今日算法系列，题解更新地址：https://studeyang.tech/2023/0718.html