java根据前、中序遍历结果重新生成二叉树

1、首先写一个类表示二叉树

public class TreeNode {int num;TreeNode left;TreeNode right;public TreeNode(int num) {this.num = num;}}

2、根据前，中序遍历，在控制台我们可以得到两个结果pre 和 in：

 /*** 前序遍历* @param node*/public static void PreTree(TreeNode node){if (node == null){return;}System.out.println(node.val);PreTree(node.left);PreTree(node.right);}/*** 中序遍历* @param node*/public static void MidTree(TreeNode node){if (node == null){return;}PreTree(node.left);System.out.println(node.val);PreTree(node.right);}public static void main(String[] args) {TreeNode head = new TreeNode(1);head.left = new TreeNode(2);head.right = new TreeNode(3);head.left.left = new TreeNode(4);head.left.right = new TreeNode(5);int[] pre = {1, 2, 4, 5, 3};int[] in = {2, 4, 5, 1, 3};}

3、接下来编写构建二叉树的方法：

/*** 根据先序和中序遍历结果建出一颗树* 先序结果是：pre[L1...R1], 中序结果是[L2...R2]*/public static TreeNode buildTreeNode(int[] pre, int[] in){if (pre == null || in == null || pre.length != in.length){return null;}return f(pre, 0, pre.length-1, in, 0, in.length-1);}/*** int[] pre = {1, 2, 4, 5, 3};* int[] in = {2, 4, 5, 1, 3};*/public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2){if (L1 > R1){return null;}// 根节点等于前序遍历的第一个数TreeNode head = new TreeNode(pre[L1]);if (L1 == R1){return head;}int find = L2;while (in[find] != pre[L1]){find++;}head.left  = f(pre,L1 + 1, L1 + find - L2, in, L2, find - 1);head.right = f(pre, L1 + find - L2 + 1, R1, in, find+1, R2);return head;}

4、由于上面使用了while循环遍历，该方法还可以进一步优化为：

/*** 根据先序和中序遍历结果建出一颗树* 先序结果是：pre[L1...R1], 中序结果是[L2...R2]*/public static TreeNode buildTreeNode1(int[] pre, int[] in){if (pre == null || in == null || pre.length != in.length){return null;}HashMap<Integer, Integer> valueIndexMap = new HashMap<>();for (int i = 0; i < in.length; i++) {valueIndexMap.put(in[i], i);}return g(pre, 0, pre.length-1, in, 0, in.length-1, valueIndexMap);}public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2, HashMap<Integer, Integer> valueIndexMap){if (L1 > R1){return null;}TreeNode head = new TreeNode(pre[L1]);if (L1 == R1){return head;}int find = valueIndexMap.get(pre[L1]);head.left  = g(pre,L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);head.right = g(pre, L1 + find - L2 + 1, R1, in, find+1, R2, valueIndexMap);return head;}