【算法训练-二叉树 二】【重建二叉树】依据前序与中序遍历序列重建二叉树

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【重建二叉树】，使用【二叉树】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

依据前序与中序遍历序列重建二叉树【MID】

依据前序和中序的特性查找

题干

解题思路

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位

1. 首先通过前序遍历拿到当前树的根节点

对应题目中的结果就是：

2. 因为中序遍历中根节点的左边是左子树，右边是右子树，所以可以依据根节点在中序遍历中的位置，知道左右子树的范围

代码实现

给出代码实现基本档案

基本数据结构：二叉树
辅助数据结构：哈希表
算法：递归
技巧：无

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    // 0 设置中序遍历 值-元素位置 的map，因为题目确保了无重复元素
    private Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // 1 条件判断
        if (preOrder == null || preOrder.length < 1 || vinOrder == null ||
                vinOrder.length < 1) {
            return null;
        }
        // 2 构建中序遍历的哈希映射
        int length = preOrder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(vinOrder[i], i);
        }
        // 递归获取左右子树
        return rebuildTree(preOrder, 0, length - 1, vinOrder, 0, length - 1);
    }

    private TreeNode rebuildTree(int[] preOrder, int preLeft, int preRight,
                                 int[] inOrder, int inLeft, int inRight) {

        // 0 设置递归终止条件
        if (preLeft > preRight) {
            return null;
        }

        // 1 首先构建根节点，也就是前序遍历的第一个元素
        TreeNode root = new TreeNode(preOrder[preLeft]);
        // 找到根节点在中序集合中的位置
        int pIndex = indexMap.get(preOrder[preLeft]);
        // 明确左子树的节点数量
        int leftSize = pIndex - inLeft;

        // 2 递归构建根节点的左子树:
        root.left = rebuildTree(preOrder, preLeft + 1, preLeft + leftSize,
                                inOrder, inLeft, pIndex - 1);

        // 3 递归构建根节点的右子树:
        root.right = rebuildTree(preOrder, preLeft + leftSize + 1, preRight,
                                 inOrder, pIndex + 1, inRight);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

复杂度分析

时间复杂度：遍历了一遍二叉树，时间复杂度O（N）；
空间复杂度：使用了辅助数据结构哈希表，空间复杂度O（N），递归栈深度极端情况下为O（N），综合来看还是O（N）