1、根据前序和中序遍历重构二叉树

1.1 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

1.2 题目分析

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的右边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，找到根结点的值，也就区分出左右子树的大小、位置。

1.3 代码实现

import java.util.HashMap; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class ReconstructTree { public static TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre==null && in==null){ return null; } HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < in.length; i++) { map.put(in[i], i); } return solve(pre,in,0,pre.length-1,0,in.length-1,map); } public static TreeNode solve(int[] pre,int[] in,int preL,int preR,int inL,int inR,HashMap<Integer, Integer> map){ if(preL>preR||inL>inR){ return null; } TreeNode head = new TreeNode(pre[preL]); int numl = map.get(pre[preL]); head.left = solve(pre, in, preL+1, preL+numl-inL, inL, numl-1,map); head.right = solve(pre, in, preL+numl-inL+1, preR, numl+1, inR,map); return head; } public static void main(String[] args) { int[] a = {1,2,4,7,3,5,6,8}; int[] b = {4,7,2,1,5,3,8,6}; TreeNode node = reConstructBinaryTree(a, b); } }

2、根据中序和后序遍历重构二叉树

2.1 题目分析

中序和后序重构的过程与先序和中序的过程类似。先序和中序的过程是用先序数组最左的值来对中序数组进行划分，因为这里头节点的值。后序数组中头节点的值是后序数组最右的值，所以用后序最右的值来划分中序数组。

2.2 代码实现

//根据中序和后序数组重构二叉树 public static TreeNode inPosToTree(int[] in,int[] pos){ if(in==null || pos==null){ return null; } HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < in.length; i++) { map.put(in[i], i); } return solve2(in, pos, 0, in.length-1, 0, pos.length-1,map); } public static TreeNode solve2(int[] in,int[] pos,int inL,int inR,int posL,int posR,HashMap<Integer, Integer> map){ if(inL>inR||posL>posR){ return null; } TreeNode node = new TreeNode(pos[posR]); int num = map.get(node.val); node.right = solve2(in, pos, num+1, inR, posR+num-inR, posR-1,map); node.left = solve2(in, pos, inL, num-1, posL, posR+num-1-inR, map); return node; }

3、通过先序和后序重构二叉树

3.1 题目

通过先序和后序重构二叉树，但大多数情况下并不能通过这两个数组把原来的树重构出来。这是因为很多结构不同的树中，先序与后序数组是一样的。

3.2 题目分析

然后需要分析出什么样的树可以被先序和后序数组重建，如果一棵二叉树除叶节点之外，其他所有的节点都有左孩子和右孩子，只有这样的树才可以被先序和后序数组重构出来。最后通过划分左右子树各自的先序与后序数组的方式重构整棵树。

3.3 代码实现

//根据前序和后序遍历重构二叉树 public static TreeNode proPosToTree(int[] pro,int[] pos){ if(pro==null || pos==null){ return null; } HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < pos.length; i++) { map.put(pos[i], i); } return solve3(pro, pos, 0, pro.length-1, 0, pos.length-1, map); } public static TreeNode solve3(int[] pro,int[] pos,int proL,int proR,int posL,int posR,HashMap<Integer, Integer> map){ TreeNode head = new TreeNode(pos[posR--]); if(proL==proR){ return head; } int num = map.get(pro[++proL]); head.left = solve3(pro, pos, proL, proL+num-posL, posL, num, map); head.right = solve3(pro, pos, proL+num-posL+1, proR, num+1, posR, map); return head; }