本文共 5317 字，大约阅读时间需要 17 分钟。
题目：请用递归方式实现二叉树的先序、中序和后序的遍历打印。给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。
思路：使用递归来遍历二叉树很简单，思考时只要对一棵树进行思考就可以，不要展开递归（注意，考虑递归时总是从逻辑功能上来思考问题，不要从递归展开细节上来思考问题）
代码一：
由于树有多少个结点事先是不知道的，因此在遍历二叉树的结点时不能将结点存放在数组中，因为数组大小不知，因此数组无法创建；
常识①：对于一维数组，创建是必须明确数组的大小，否则无法创建，例如int[] res=new int[10];对于二维数组，在创建时不一定要明确2个维度的大小，第一个维度的大小必须确定，表示有多少行，第二个维度可以先空着不写，例如int[][] res=new int[3][]；可以res数组的每个元素都是一个数组，因此为其赋值时必须明确其为数组，例如res[0]=new int[10];或者将一个已经创建好的数组int[] array=new int[10]; 赋值给它：res[0]=array；因此这里由于每个树有多少集合不确定因此只能使用集合。
常识②：集合list等的遍历可以使用迭代器Iterator<Integer> iterator=list1.iterator();也可以使用for循环遍历，通过list.get(i)来获取指定下标的元素。
常识③：集合list等可以使用toArray()方法直接转换为数组，但是注意list.toArray()得到的是一个Object[]类型的数组，同时注意，数组是不可以进行强制类型转换的，例如Integer []res=(Integer[])list.toArray()是无法成功的，只有单个对象才可以进行强制类型转换；要转换为指定类型的数组需要使用参数来指定：先建立一个要转换的类型的数组，注意必须是包装类的数组，不能是基本类型的数组。Integer array=new Integer[10]；然后使用集合list的toArray()方法，同时传入建立的目标类型对象的数组array，这样jvm会将object[]类型数组自动转换为Integer[]类型数组：Integer[] res=list.toArray(array)；注意，这样得到的类型是Integer[]的数组，而无法转变为int[]数组，如果要求返回int[]那么返回Integer[]是无法自动拆箱返回的。即返回类型不会自动拆箱装箱，只有在赋值、运算时才会自动装箱、拆箱。因此本题中要去返回int[]而通过toArray()得到的只能是Integer[],最后还是通过遍历list将元素逐个取出放入数组中来解决的。
常识④：这里创建的List<>list的类型可以是Integer，但是最好是TreeNode，即集合list用来存放结点的集合，注意，可以将二叉树上遍历过的结点一次放入到集合中，并且同一个结点对象可以放入到多个不同的list集合中，注意理解：所谓将结点对象放入到list集合中只是指将对这个结点对象的一个引用存放到集合中，即在集合中存放一个指向该结点对象的地址指针，并不是将对象真的放入集合，当一个对象放入到集合中之后，这个对象就被集合引用了，只要集合存在这个引用就会存在，从而GC不会回收被引用的对象。
import java.util.*;/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*///由于树元素数目不知道因此开始只能使用集合来接受元素，结束后再转换为数组进行返回public class TreeToSequence { public int[][] convert(TreeNode root) { List list1=new ArrayList<>(); List list2=new ArrayList<>(); List list3=new ArrayList<>(); //先序遍历,将遍历的结果放入到list1中后返回 this.preOrderRecru(root,list1); //中序遍历,将遍历的结果放入到list2中后返回 this.inOrderRecru(root,list2); //后序遍历,将遍历的结果放入到list3中后返回 this.postOrderRecru(root,list3); //创建二维数组用来存放结果 int[][] results=new int[3][list1.size()]; //集合转数组只能转成Integer包装类型，不能转为基本类型，必须从集合中逐个取出 //遍历集合要使用迭代器 Iterator iterator=list1.iterator(); int i=0; while(iterator.hasNext()){ //可以不强转,编译器会自动拆箱 results[0][i++]=(int)iterator.next(); } iterator=list2.iterator(); i=0; while(iterator.hasNext()){ results[1][i++]=iterator.next(); } iterator=list3.iterator(); i=0; while(iterator.hasNext()){ results[2][i++]=iterator.next(); } //返回结果 return results; } //该方法用来将以TreeNode为根结点的二叉树先序遍历后放入list1中 private void preOrderRecru(TreeNode treeNode,List list){ //这是一个递归方法，要有结束的边界条件,当没有子节点时返回 if(treeNode==null) return; //①先遍历子树的根结点 list.add(treeNode.val); //②递归遍历根结点的左子树 this.preOrderRecru(treeNode.left,list); //③递归遍历根结点的右子树 this.preOrderRecru(treeNode.right,list); } //该方法用来将以TreeNode为根结点的二叉树中序遍历后放入list2中 private void inOrderRecru(TreeNode treeNode,List list){ //这是一个递归方法，要有结束的边界条件,当没有子节点时返回 if(treeNode==null) return; //①先遍历子树的左子树 this.inOrderRecru(treeNode.left,list); //②遍历根结点放入list中 list.add(treeNode.val); //③遍历子树的右子树 this.inOrderRecru(treeNode.right,list); } //该方法用来将以TreeNode为根结点的二叉树后序遍历后放入list3中 private void postOrderRecru(TreeNode treeNode,List list){ //这是一个递归方法，要有结束的边界条件,当没有子节点时返回 if(treeNode==null) return; //①先遍历子树的左子树 this.postOrderRecru(treeNode.left,list); //②遍历子树的右子树 this.postOrderRecru(treeNode.right,list); //③遍历根结点放入list中 list.add(treeNode.val); }} 代码二：import java.util.*;/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*///使用递归遍历二叉树public class TreeToSequence { public int[][] convert(TreeNode root) { //创建集合list，将遍历过的二叉树结点都存放到集合中，list是有序的 List preOrderList=new ArrayList (); List inOrderList=new ArrayList (); List afterOrderList=new ArrayList (); //从根结点treeNode开始先序遍历，将遍历过的结点放入preNodeList集合中 this.preOrder(root,preOrderList); this.inOrder(root,inOrderList); this.afterOrder(root,afterOrderList); //建立一个二维数组，返回结果,二维数组可以先指定一维大小 int[][]results=new int[3][preOrderList.size()]; //集合list无法直接转化为int[]数组，因此要通过逐个遍历取出再赋值给数组 for(int i=0;i preOrderList){ //递归的终止条件 if(root==null) return; //①遍历根结点 preOrderList.add(root); //②遍历左子树 this.preOrder(root.left,preOrderList); //遍历右子树 this.preOrder(root.right,preOrderList); } //该方法用来从根结点root开始中序遍历二叉树，将遍历过的结点放入到集合inOrderList中 private void inOrder(TreeNode root,List inOrderList){ //递归的终止条件 if(root==null) return; //①遍历左子树 this.inOrder(root.left,inOrderList); //②遍历根结点 inOrderList.add(root); //遍历右子树 this.inOrder(root.right,inOrderList); } //该方法用来从根结点root开始后序遍历二叉树，将遍历过的结点放入到集合afterOrderList中 private void afterOrder(TreeNode root,List afterOrderList){ //递归的终止条件 if(root==null) return; //①遍历左子树 this.afterOrder(root.left,afterOrderList); //②遍历右子树 this.afterOrder(root.right,afterOrderList); //③遍历根结点 afterOrderList.add(root); }}