数据结构与算法之从前序与中序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树

试题部分

做表法【做完之后一定要验证】

主要内容就是使用做表法来快速确定二叉树的结构，这里贴上up主原视频链接：

无脑秒解！已知先/后序遍历与中序遍历，求后/先序遍历。_哔哩哔哩_bilibili

原则：

1. 两个序列中必须含有中序遍历序列才能确定唯一的二叉树序列
2. 在表格中：
   1. 中序遍历序列表示表格的行表头(首行)
   2. 前/后序遍历表示表格的列表头(首列)，其中后序遍历需要调转序列次序
3. 左子树所有结点在父母结点左边(你根据下标来)
4. 右子树所有结点在父母结点右边(你根据下标来)

例子

如下图：

编码部分(leetcode)

题目

leetcode原地址：从前序与中序遍历序列构造二叉树

---

官方题解说明：
从前序与中序遍历序列构造二叉树 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

步骤解析

1. 首先根据前序遍历序列第一位作为根节点，并且从中序遍历序列中找到这个数，将序列划分为左中右三个部分
2. 根据第一步找到的左中右，分别在计算得出左序列的左中右部分、右序列的左中右部分
3. 如此循环往复，直到左部分长度为1、右部分长度为1，结束该算法。

---

代码部分

/**  
 * 根据前序遍历序列和中序遍历序列生成对应的二叉树  
 *  
 * @param preSequence 前序遍历序列  
 * @param midSequence 中序遍历序列  
 * @return 对应的二叉树  
 */  
TreeNode generateTreeByMidAndPreSequence(int[] preSequence, int[] midSequence) {  
    if (preSequence == null || midSequence == null) {  
        return null;  
    }  
    LinkedHashMap linkedHashMap = new LinkedHashMap<>();  
    for (int i = 0; i < midSequence.length; i++) {  
        linkedHashMap.put(midSequence[i], i);  
    }  
    int pIndex = linkedHashMap.get(preSequence[0]);  
    //根据获得的根节点，传入前序遍历序列以及中序遍历序列进行构建二叉树的构建  
    TreeNode rootNode = recursion(preSequence, 0, preSequence.length - 1, linkedHashMap, 0, midSequence.length - 1);  
    return rootNode;  
}  
  
/**  
 * 递归体函数，通过下标来控制传入方法序列的大小  
 *  
 * @param preSequence   前序遍历序列  
 * @param preLeft       前序遍历序列起始位  
 * @param preRight      前序遍历序列结束位  
 * @param linkedHashMap 记录表，避免再次迭代浪费时间  
 * @param midLeft       中序遍历序列起始位  
 * @param midRight      中序遍历序列结束位  
 * @return 根据当前传入序列创建对应的二叉树  
 */  
private TreeNode recursion(int[] preSequence, int preLeft, int preRight, LinkedHashMap linkedHashMap, int midLeft, int midRight) {  
    if (preLeft > preRight || midLeft > midRight) {  
        return null;  
    }  
    int rootVal = preSequence[preLeft];  
    TreeNode rootNode = new TreeNode(rootVal);  
    int pIndex = linkedHashMap.get(rootVal);  
    //前左子树构建  
    rootNode.left = recursion(preSequence, ++preLeft, pIndex - midLeft + preLeft, linkedHashMap, midLeft, pIndex - 1);  
    rootNode.right = recursion(preSequence, pIndex - midLeft + preLeft + 1, preRight, linkedHashMap, pIndex + 1, midRight);  
    return rootNode;  
}
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

‍