剑指offer：重建二叉树

前言

牛客网剑指offer的66道题，刷起来！每道题会提供简单的思路以及测试通过的代码

题目描述

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

二叉树结构：

1 class TreeNode {
2     int val;
3     TreeNode left;
4     TreeNode right;
5     TreeNode(int x) { val = x; }
6 }

注：点击左下角的阅读原文即可跳转到原文，可以提交代码

解答思路

前序遍历序列的第一个元素 1 就是二叉树的根节点，中序遍历序列的根节点 1 把这个序列分成两半部分，分别是[4,7,2]和[5,3,8,6]，左半分部是根节点的左子树，右半分布是根节点的右子树。

基于这个特点，我们可以采用递归的方法来做，如果对递归的使用不是很熟的，建议看我之前的链表打卡链表打卡汇总，很多题都用到了递归，其大致逻辑如下。

1、通过前序序列第一个元素确定根节点(例如 1)。

2、通过根节点把中序序列分成两个序列，一个是左子树序列([4,7,2)]，一个是右子树序列([5,3,8,6)]。

3、通过左右子树的中序序列可以求出前序遍历的左右子树序列(左:[2,4,7],右:[3,5,8,6])。

4、左右子树的前序序列第一个元素分别是根节点的左右儿子。

5、通过递归重复以上步骤(看代码吧，看了代码可能就好理解点了)。

 1    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
 2        TreeNode root;
 3        root = rebuildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
 4
 5        return root;
 6    }
 7    // preStart-preEnd表示前序序列的起始位置，inStart-inEnd也一样
 8    private TreeNode rebuildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
 9        if(preStart > preEnd | inStart > inEnd)
10            return null;
11        // 根节点
12        TreeNode root = new TreeNode(pre[preStart]);
13        // 寻找根节点在中序序列的位置
14        for (int i = inStart; i <= inEnd; i++) {
15            if (in[i] == pre[preStart]) {
16                // 可以计算出中序序列的左右子树序列为:左：inStart~i -1，右：i+1~inEnd。
17                // 前序序列的左右子树：左：preStart+1~preStart+i-inStart，右：preStart+i-inStart+1~preEnd
18                root.left = rebuildTree(pre,preStart+1, preStart+i-inStart,in, inStart, i - 1);
19                root.right = rebuildTree(pre,preStart+i-inStart+1, preEnd, in, i+1, inEnd);
20            }
21        }
22        return root;
23    }

往期