根据一个树的中序遍历和前序遍历数据，还原一个二叉树的思考

根据一个树的中序遍历和前序遍历数据，还原一个二叉树的思考。

一般树的通常遍历一共有四种：前序，中序，后序，层次遍历；中序遍历和其他任何一个两个遍历序列就可以唯一确定一颗二叉树。

下面的代码基于递归实现是完全没有问题的。可运行。

package com.mytest.test001; import java.util.Arrays; //树节点的定义 class BTree{ BTree left; BTree right; int val; } public class ConstructTreefromcol { public static void main(String[] args) throws Exception { int[] preorder={1,2,4,7,3,5,6,8}; int[] inorder={4,7,2,1,5,3,8,6}; BTree root=ConstructTree(preorder,inorder);; } private static BTree ConstructTree(int[] preorder, int[] inorder) throws Exception { if(preorder==null || inorder==null) return null; if(preorder.length!=inorder.length) throw new Exception("输入的中序和前序遍历不对"); BTree root=new BTree(); //法1 for(int i=0;i<inorder.length;i++){ if(inorder[i]==preorder[0]){ root.val=inorder[i]; System.out.println(root.val); root.left=ConstructTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right=ConstructTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); } } return root; } }

针对上面的代码我们做些小的调整试试，将红色部分修改为如下代码： 第一种改法！  报错，数组越界：

int i=0; while(i<inorder.length){ if(inorder[i]!=preorder[0]) {i++;} if(inorder[i]==preorder[0]){ break; } } root.val=preorder[0]; System.out.println(root.val); root.left=ConstructTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right=ConstructTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); 都是找到i的位置，为何越界？当左右子树一个为空，则访问 root.val=preorder[0]出错。

正确添加一个判断即为：

int i=0; while(i<inorder.length){ if(inorder[i]!=preorder[0]) {i++;} if(inorder[i]==preorder[0]){ break; } } if(i<inorder.length){ //很重要，这个必须有 root.val=preorder[0]; System.out.println(root.val); root.left=ConstructTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right=ConstructTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); } 第二种改法：

int i=0; while(inorder[i]!=preorder[0] && i<inorder.length){ i++; } if(i<inorder.length){ root.val=preorder[0]; System.out.println(root.val); root.left=ConstructTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right=ConstructTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); } 任然是数组越界：

这个正确写法是将while循环中的前后顺序需要兑换。

int i=0; while( i<inorder.length && inorder[i]!=preorder[0]){ i++; } if(i<inorder.length){ root.val=preorder[0]; System.out.println(root.val); root.left=ConstructTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right=ConstructTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); } 是不是有什么启发呢？虽然是很简单的问题，但是细节很重要。你需要几秒钟能发现问题呢？不同的写法，细节上有很多隐含的东西，使用for循环第一种写法，暗含了对左右为空的处理，健壮性较好，后面的改写，需要注意诸多细节才能调试成功！