题目
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字，例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出二叉树并输出它的头结点。
利用递归的方法构建，其实没有想象的那么难，主要是理解构建过程就行！！
思想构建过程
题目中前序遍历的第一个节点{1}一定是这棵二叉树的根节点，根据中序遍历序列，可以发现中序遍历序列中节点{1}之前的{4,7,2}是这棵二叉树的左子树，{5,3,8,6}是这棵二叉树的右子树。然后，对于左子树，递归地把前序子序列{2,4,7}和中序子序列{4,7,2}看成新的前序遍历和中序遍历序列。此时，对于这两个序列，该子树的根节点是{2}，该子树的左子树为{4,7}、右子树为空，如此递归下去（即把当前子树当做树，又根据上述步骤分析）。{5,3,8,6}这棵右子树的分析也是这样。
实现
二叉树结点 BinaryTreeNode
//二叉树节点 public class BinaryTreeNode { public int data; public BinaryTreeNode left; public BinaryTreeNode right; public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right){ super(); this.data = data; this.left = left; this.right = right; } public BinaryTreeNode(int data){ this.data = data; } }
构建
package lms.datastructure.tree; import java.util.Arrays; public class ConstructTree { public static BinaryTreeNode reConstruct(int[] preOrder, int[] inOrder) { if (preOrder == null || inOrder == null) { return null; } //从先序遍历中取出根节点，构造二叉树 int rootData = preOrder[0]; BinaryTreeNode root = new BinaryTreeNode(rootData); root.left = root.right = null; //只有一个数字情况 也是递归的终止条件 if (preOrder.length == 1 && inOrder.length == 1) { if (inOrder[0] == preOrder[0]) { return root; } else { throw new IllegalArgumentException("invalid input"); } } //中序中找到 int rootinIndex = 0; while (rootinIndex < inOrder.length && rootData != inOrder[rootinIndex]) { rootinIndex++; } //同样的方法递归左右子树 //中序中位置判断是否有左子树 if (rootinIndex > 0) { root.left = reConstruct( Arrays.copyOfRange(preOrder, 1, rootinIndex + 1), Arrays.copyOfRange(inOrder, 0, rootinIndex)); } //判断结点有右子树 if (rootinIndex < inOrder.length - 1) { root.right = reConstruct( Arrays.copyOfRange(preOrder, rootinIndex + 1, preOrder.length), Arrays.copyOfRange(inOrder, rootinIndex + 1, inOrder.length) ); } //返回构造的根结点 return root; } //=====后序遍历============ //递归 后序 public static void postOrderRecur(BinaryTreeNode root) { if (null != root) { postOrderRecur(root.left); postOrderRecur(root.right); System.out.print(root.data + " "); } } public static void main(String[] args) { /** * 1 * / \ * 2 3 * / / \ * 4 5 6 * \ / * 7 8 */ int[] pre = {1, 2, 4, 7, 3, 5, 6, 8}; int[] in = {4, 7, 2, 1, 5, 3, 8, 6}; BinaryTreeNode root = reConstruct(pre, in);
//后序遍历构造后的二叉树
postOrderRecur(root);
}
}
输出结果
7 4 2 5 8 6 3 1
结果为后序遍历结果