剑指Offer 7. 重建二叉树

发表于 | 更新于 | 分类于 | 阅读次数：

题目

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建出二叉树并输出它的头结点。

解答1[Java]：递归

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
import java.util.HashMap;

public class Solution {
    // 缓存中序遍历数组每个值对应的索引
    private HashMap<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 reConstructBinaryCore(pre, 0, pre.length - 1, 0);
    }

    private TreeNode reConstructBinaryCore(int[] pre, int leftOfPre, int rightOfPre, int leftOfIn) {
        if (leftOfPre > rightOfPre)
            return null;
        TreeNode root = new TreeNode(pre[leftOfPre]); // pre[preL]存的是根节点的值
        int posOfRoot = indexForInOrders.get(root.val); // 获取根节点在中序遍历序列中的位置
        int leftTreeSize = posOfRoot - leftOfIn;
        root.left = reConstructBinaryCore(pre, leftOfPre + 1, leftOfPre + leftTreeSize, leftOfIn);
        root.right = reConstructBinaryCore(pre, leftOfPre + leftTreeSize + 1, rightOfPre, leftOfIn + leftTreeSize + 1);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

曾经想把这里：

1
2
if (leftOfPre > rightOfPre)
    return null;

修改为 if (leftOfPre == rightOfPre)，后来发现不行，因为 leftOfPre 和 rightOfPre 不是线性变化的，有可能不会出现两者相等的情况。例如，如果一颗只有左子树没有右子树的二叉树，第一次递归的时候在重建右子树的时候就会导致 leftOfPre 大于 rightOfPre。

另外一道类似的题目：[编程题]二叉树遍历 - 牛客网