Java实现：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：1. 当前序遍历序列（pre）和中序遍历序列(in)为空时，返回一个空二叉树；2. 采用递归的思想，前序遍历序列(pre)的第一个结点为二叉树的根结点，先找出该根节点，定义为root根结点，并赋值给val，然后遍历中序遍历序列(in)，找出val的位置，将其索引赋值给index；根据index对中序遍历序列(in)进行划分，将0-index（不包含index）的子序列划分为LeftIn，将index+1-in.length的子序列划分为RightIn; 根据LeftIn子序列和RightIn子序列的长度对前序遍历序列（pre）进行划分，将1-LeftIn.length+1的子序列划分为LeftPre，将index+1-pre.length的子序列划分为RightPre; 然后根据LeftPre子序列和LeftIn子序列构造二叉树左子树，根据RightPre子序列和RightIn子序列构造二叉树右子树；依次往下，直到整个二叉树构造完成；
例：前序遍历序列{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，构造的二叉树如下：
代码如下，为展示二叉树构造结果，输出后续遍历序列:
1 import java.util.Arrays; 2 import java.util.Scanner; 3 4 class TreeNode { 5 int val; 6 TreeNode left; 7 TreeNode right; 8 TreeNode(int x) { 9 val = x; 10 } 11 } 12 13 public class Solution { 14 public static void main(String[] args) { 15 Scanner scanner = new Scanner(System.in); 16 String[] str1 = scanner.nextLine().split(" "); 17 String[] str2 = scanner.nextLine().split(" "); 18 // 先序遍历序列 19 int[] pre = new int[str1.length]; 20 // 中序遍历序列 21 int[] in = new int[str2.length]; 22 for(int i=0 ; i<str1.length ; i++) { 23 pre[i] = Integer.parseInt(str1[i]); 24 in[i] = Integer.parseInt(str2[i]); 25 } 26 TreeNode root = null; 27 root = reConstructBinaryTree(pre, in); 28 posttraverse(root); 29 System.out.println(); 30 } 31 32 public static TreeNode reConstructBinaryTree(int [] pre, int [] in) { 33 if(pre.length == 0 && in.length == 0) 34 return null; 35 int val = pre[0]; 36 TreeNode root = new TreeNode(val); 37 int index = 0; 38 for(int i=0 ; i<in.length ; i++){ 39 if(in[i]==val) 40 index = i; 41 } 42 int[] LeftIn = Arrays.copyOfRange(in, 0, index); 43 int[] RightIn = Arrays.copyOfRange(in, index+1, in.length); 44 int[] LeftPre = Arrays.copyOfRange(pre, 1, LeftIn.length+1); 45 int[] RightPre = Arrays.copyOfRange(pre, index+1, pre.length); 46 root.left = reConstructBinaryTree(LeftPre, LeftIn); 47 root.right = reConstructBinaryTree(RightPre, RightIn); 48 return root; 49 } 50 // 后序遍历输出 51 public static void posttraverse(TreeNode root) { 52 if(root == null) 53 return; 54 posttraverse(root.left); 55 posttraverse(root.right); 56 System.out.print(root.val + " "); 57 } 58 }
以上面例子为例，输出的后续遍历序列为{7,4,2,5,8,6,3,1}，结果如下：