填图问题：如果已知一个二叉树的前相遍历和中相遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后相遍历为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
答案： DGEBHFCA。
解决问题的过程：
一、基本概念盲：对一棵二叉树进行遍历，我们可以进行三中序遍历。 分别为前序扫描、中序扫描、后序扫描。
超前遍历：根节点-左节点-右节点
中顺序扫描：左节点-根节点-右节点
后续遍历：左节点-右节点-根节点
根节点为yjfdts，前序由大哥带头，中序由大哥居中指挥，后序由大哥坐在镇后。
二、分析前序和中序特点：
1、前序的第一个节点，必然是大哥
2、哥哥中序必在中间，自然可以将中序分为左右两个子树；
3、对左右子树重复以上过程，最终一定能还原整个二叉树。
三.向后遍历二叉树。
四、理论结束后，回到主题：
前扫描： ABDEGCFH
中序扫描： DBGEACHF
1、从前序中发现哥哥： a，左子树为： DBGE，右子树： CHF
a
//
DBGE CHF
2、左子树递归，按照前面的顺序找到哥哥： b，左子树左子树为： d，左子树右子树为： GE
a
//
B CHF
//
D GE
3、不需要递归到左子树左子树。 只有一个节点d递归到左边子树的右边子树，从前面的顺序开始找到哥哥： e。 然后左边的子树右边的子树是： g
a
//
B CHF
//
D E
/
g
4、左侧树递归结束，右侧树依葫芦画葫芦，最终恢复的二叉树就是它。
a
//
B C
33
D E F
//
G H
5、将其推迟： DGEBHFCA
那么，以上就是解决问题的全过程。 作为程序员，你应该充分利用手头的工具解开——计算机。 因此，我们有必要进一步对这个问题进行模型化，考虑模型的算法。 巧的是，let code的第105个问题就是这个主题。 大家可以试着解决问题。 这里展示了最简单的递归算法的实现。
/**二叉树结构通过前相遍历、中相遍历获得二叉树* @author wulf */public
class BTree { /** * 构造二叉树 * * @param preOrder 前序遍历数组 * @param inOrder 中序遍历数组 * @return */ public TreeNode buildTree(String[] preOrder, String[] inOrder) { return buildTreeByRecursion(preOrder, 0, preOrder.length, inOrder, 0, inOrder.length); } /** * 递归构造二叉树 * * @param preOrder 前序遍历数组 * @param preOrderStart * @param preOrderEnd * @param inOrder 中序遍历数组 * @param inOrderStart * @param inOrderEnd */ private TreeNode buildTreeByRecursion(String[] preOrder, int preOrderStart, int preOrderEnd, String[] inOrder, int inOrderStart, int inOrderEnd) { if (preOrderStart == preOrderEnd) { return null; } // 根节点值 String rootValue = preOrder[preOrderStart]; // 构造根节点 TreeNode rootNode = new TreeNode(rootValue); // 在中序遍历中找到根节点位置 int rootIndex = 0; for (int i = inOrderStart; i < inOrderEnd; i++) { if (inOrder[i].equals(rootValue)) { rootIndex = i; break; } } int leftNum = rootIndex - inOrderStart; // 递归的构造左子树 rootNode.left = buildTreeByRecursion(preOrder, preOrderStart + 1, preOrderStart + leftNum + 1, inOrder, inOrderStart, rootIndex); // 递归的构造右子树 rootNode.right = buildTreeByRecursion(preOrder, preOrderStart + leftNum + 1, preOrderEnd, inOrder, rootIndex + 1, inOrderEnd); return rootNode; } /** * 后续遍历 * * @param treeNode 二叉树对象 */ private void postOrder(TreeNode treeNode) { if (treeNode != null) { postOrder(treeNode.left); postOrder(treeNode.right); System.out.print(treeNode.val + " "); } } /** * 测试 * * @param args */ public static void main(String[] args) { String[] preOrder = {"A", "B", "D", "E", "G", "C", "F", "H"}; String[] inOrder = {"D", "B", "G", "E", "A", "C", "H", "F"}; BTree bTree = new BTree(); TreeNode treeNode = bTree.buildTree(preOrder, inOrder); System.out.println("二叉树：" + treeNode); System.out.println("后续遍历："); bTree.postOrder(treeNode); } /** * 二叉树对象 */ private class TreeNode { String val; //节点数据 TreeNode left; //左节点 TreeNode right; //右节点 TreeNode() { } TreeNode(String val) { this.val = val; } TreeNode(String val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } public String toString() { StringBuilder sb = new StringBuilder(); sb.append(val); sb.append(","); sb.append(left); sb.append(","); sb.append(right); return sb.toString(); } } }运行结果：
二叉树：A,B,D,null,null,E,G,null,null,null,C,null,F,H,null,null,null 后续遍历： D G E B H F C A