二叉树的遍历方式常见的三种是：先序遍历(ABC)、中序遍历(BAC)、后序遍历(BCA)
先序遍历：
若二叉树为空，则空操作；否则：
访问根结点;先序遍历左子树；先序遍历右子树。中序遍历：
若二叉树为空，则空操作；否则：
中序遍历左子树；访问根结点；中序遍历右子树。后序遍历：
若二叉树为空，则空操作；否则：
后序遍历左子树；后序遍历右子树；访问根结点。在学习到 根据遍历序列确定二叉树 时，知道了：可以通过二叉树的先中或者中后遍历序列唯一确定一棵二叉树。
根据算法描述 使用java 码出依据中后遍历序列来获取先序遍历序列的代码：
1 package learn.normalcode; 2 3 import java.util.ArrayList; 4 5 public class BlankD { 6 public static ArrayList<Character> ansList = new ArrayList<>(11); 7 //通过二叉树的中序序列和后序序列获取前序序列 8 public static void getAns(String middle, String back) { 9 //后序序列的最后一个结点为根结点10 int backLength = back.length(), middleLength = middle.length();11 char c = '#';12 if (backLength > 0) {13 c = back.charAt(backLength - 1);14 ansList.add(c);15 16 //从中/后序序列中分裂出左右子树的中/后序序列17 int indexOfRoot = middle.indexOf(c);18 getAns(middle.substring(0, indexOfRoot), back.substring(0, indexOfRoot));19 getAns(middle.substring(indexOfRoot + 1, middleLength), back.substring(indexOfRoot, backLength - 1));20 }21 return;22 23 }24 public static void main(String[] args) {25 String middle = "SMBDCEAFHG", back = "MSDECBHGFA";26 getAns(middle, back);27 System.out.println(ansList);28 29 ansList.clear();30 middle = "DCBA";31 back = "DCBA";32 getAns(middle, back);33 System.out.println(ansList);34 35 ansList.clear();36 middle = "SMBDCEA";37 back = "MSDECBA";38 getAns(middle, back);39 System.out.println(ansList);40 }41 }
转载于:https://www.cnblogs.com/orzt/p/11529865.html