根据前中序遍历重建二叉树(java)
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
题目链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
题解：
首先要清楚前序、中序、后序遍历的概念，这里只要记住主语说的是根就可以了，前序就是根在前，以此类推。
也许有人和我一样，给这样一道题，自己用脑子很快就可以推出，但就是编程实现没有思路。经过认真分析人为操作的步骤，发现可以用递归处理。如pre{1,2,4,7,3,5,6,8},in{4,7,2,1,5,3,8,6},
首先根据前序第一为根原则，推出1为根，然后在中序中就可以推出左根的中序为{4,7,2},右根的中序{5,3,8,6},应用在前序即退出左根的前序{2,4,7},右根前序{3,5,6,8},同理往下推理一样，递归就出来了。
找出递归终止条件：当pre和in为空（length=0）,返回null即可。
然后就是将int数组划分的问题，写一个封装函数
int[] subArray(int[] array,int startindex,int num)。
代码如下：
public class Main{
public static void main(String[] args) {
int[] pre = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
TreeNode bt = new Main().ToTB(pre,in);
TreeOperation.show(bt);
}
//关键 使用递归
public TreeNode ToTB(int[] pre,int[] in){
if(pre.length==0){
return null;
}
TreeNode treeNode = new TreeNode(pre[0]);
treeNode.left = ToTB(subArray(pre,1,getIndex(in,pre[0])),subArray(in,0,getIndex(in,pre[0])));
treeNode.right = ToTB(subArray(pre,1+getIndex(in,pre[0]),pre.length-getIndex(in,pre[0])-1),subArray(in,getIndex(in,pre[0])+1,in.length-getIndex(in,pre[0])-1));
return treeNode;
}
//截取数组
private int[] subArray(int[] array,int startindex,int num){
int[] retArray = new int[num];
for (int i = startindex, j = 0; i < startindex+num; i++) {
retArray[j++] = array[i];
}
return retArray;
}
//获取数组指定元素下标
private int getIndex(int[] array,int target){
for (int i = 0; i < array.length; i++) {
if(array[i]==target){
return i;
}
}
return -1;
}
}
class TreeNode {
int val;
TreeNode left = null;
TreeNode right = null;
TreeNode(int x) { val = x; }
}
//树的可视化打印参考自https://www.cnblogs.com/liulaolaiu/p/11744409.html
class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(TreeNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) {
return;
}
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.val);
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) {
return;
}
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(TreeNode root) {
if (root == null) {
System.out.println("EMPTY!");
}
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
} 输出： 
