2016国考图推85题（2016国考图推85题分析）

2016国考图推85题分析

题目描述

2016年国考中，有一道图推的题目，编号为85，题目描述如下：

已知一棵二叉树的前序遍历序列为：1，2，4，7，3，5，6，8，其中数字均不重复；请问该二叉树的中序遍历序列是什么？

解题思路

从二叉树前序遍历序列，可以知道根节点的数字为1，从中序遍历的特点，我们知道，根节点把数组分成了两个部分：左子树的所有节点和右子树的所有节点，因此我们可以通过根节点在中序遍历序列中的位置将其分成两半，从而推断出两个关键字的左右子树如何连接。

具体来说，我们可以使用递归的方法，每次找到前序遍历序列中的第一个数字，作为根节点，然后在中序遍历序列中找到该数字的位置，从而确定左子树和右子树中的节点数量。然后再递归地处理左子树和右子树即可。

以样例为例，我们知道根节点是1，于是在中序遍历序列中查找1的位置，可以发现，1将数组分成了左边的{2,4,7}和右边的{3,5,6,8}两个部分。于是我们可以进一步得知，2是左子树的根节点，4是2的左子节点，7是2的右子节点，3是右子树的根节点，5是3的左子节点，6是3的右子节点，8是6的右子节点。

代码实现

```java public static TreeNode reConstructBinaryTree(int[] pre, int[] in) { if(pre == null || in == null || pre.length != in.length) return null; return construct(pre, 0, pre.length-1, in, 0, in.length-1); } private static TreeNode construct(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { if(preStart > preEnd || inStart > inEnd) return null; TreeNode root = new TreeNode(pre[preStart]); for(int i = inStart; i <= inEnd; i++) { if(in[i] == pre[preStart]) { root.left = construct(pre, preStart+1, preStart+i-inStart, in, inStart, i-1); root.right = construct(pre, preStart+i-inStart+1, preEnd, in, i+1, inEnd); } } return root; } ```