《剑指offer》之重建二叉树
前言
今天的刷的题目是关于树结构的。为了更好的解题，我们先来了解一下前序遍历、中序遍历和后续遍历。前序遍历：就是从根节点-->左节点-->右节点 就是先从找根节点，然后找左节点。如果左节点上还有子节点，就接着找自己点的根节点，左节点，左节点这样。如下图，数字的顺序就是前序遍历的顺序。
中序遍历：左节点--> 根节点--> 右节点 中序遍历是先找树的左节点，如果左节点还有子节点，就接着找子节点的左节点，然后根节点，然后右节点。如下图：
后序遍历：左节点--> 右节点--> 根节点 就是先遍历左右节点，最后是根节点，如果左右节点还有子节点，就先遍历子节点的左节点、然后右节点，然后根节点。如图：
好了，知道了前序中序后序遍历，我们来看题目。
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析
我们首先需要创建一个二叉树的类。如下：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
}这样就可以表示一个二叉树了啦。
然后知道前序和中序。那么前序的第一个元素就是根节点，然后在中序的数组中找到根节点的位置，那么根节点左边的，都是左节点，右边的都是右节点。比如 前序 pre{1,2,4,7,3,5,6,8} 中序 in {4,7,2,1,5,3,8,6} 那么第一次，从in 中找1 的位置。那么1 的左节点树的 前序{2,4,7} 中序为{4,7,2} 那么1 的右节点树的 前序{3,5,6,8} 中序为{,5,3,8,6}
这是一次操作，然后分别对根节点的左节点和右节点，进行相同的操作。前序{2,4,7} 中序为{4,7,2} 那么根节点为2，根节点的 左节点树的 前序{4,7} 中序{4,7} 右节点树为null; .....
解法
所以采用递归的方法，找出根节点，然后分别将左节点和右节点递归存储到二叉树中。
public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int length=pre.length;
if(length==0){
return null;
}
int rootVal=pre[0];
//将当前节点存入树中
TreeNode rootNode=new TreeNode(rootVal);
for(int i=0;i<length;i++){
if(rootVal== in[i]){
rootNode.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
rootNode.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,length),Arrays.copyOfRange(in,i+1,length));
}
}
return rootNode;
}这里使用了Arrays.copyOfRange(pre,begin，end) 方法，表示中pre 数组中copy数组，从begin 索引开始，到end 结束。左闭右开。
源代码
public class Solution {
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 treeNode=reConstructBinaryTree(pre,in);
TreeOperation.show(treeNode);
}
public static void print(TreeNode treeNode){
System.out.print(treeNode.val);
if(treeNode.left !=null ){
print(treeNode.left);
}
if(treeNode.right !=null){
print(treeNode.right);
}
System.out.println();
}
public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int length=pre.length;
if(length==0){
return null;
}
int rootVal=pre[0];
//将当前节点存入树中
TreeNode rootNode=new TreeNode(rootVal);
for(int i=0;i<length;i++){
if(rootVal== in[i]){
rootNode.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
rootNode.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,length),Arrays.copyOfRange(in,i+1,length));
}
}
return rootNode;
}
}然后打印二叉树，我在网上找的代码，直接拿过来用的 参考： 按照树形结构直观地打印出一棵二叉树(Java)
public 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());
}
}
}测试
反思
这里是知道前序和中序。从中序中找到左右节点。
如果给出 中序和后序呢？中序：{4,7,2,1,5,3,8,6} 后序：{7,4,2,3,5,8,6,1}
那如果给出 前序和后序呢？前序：{1,2,4,7,3,5,6,8} 后序：{7,4,2,3,5,8,6,1}