剑指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 }本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录