题意：给出二叉树前序和中序序列，要求重构该二叉树并输出根节点。 思路：就是由前序和中序确认该二叉树的形状。 代码：
package MianShiTi_6;public class MianShiTi_6 { public static class BinaryTreeNode{ int value; BinaryTreeNode left; BinaryTreeNode right; } public static BinaryTreeNode reConstruct(int[]PReOrder , int[] inOrder) { if(PreOrder == null || inOrder == null || PreOrder.length != inOrder.length || PreOrder.length < 1){ return null; } return construct(PreOrder, inOrder, 0, PreOrder.length-1, 0, inOrder.length-1); } /* ps: */ public static BinaryTreeNode construct(int []preOrder , int []inOrder ,int ps,int pe ,int is ,int ie) { if(ps > pe){ return null; } int value = preOrder[ps]; int index = is; while (index < ie && inOrder[index] != value) { index++; } if(index > ie){ throw new RuntimeException("invalid input"+index); } BinaryTreeNode node = new BinaryTreeNode(); node.value = value; //左子树重建，主要是这个ps+index-is的确认 node.left = construct(preOrder, inOrder, ps+1, ps+index-is, is, index-1); //左子树重建，主要是这个ps+index-is+1的确认 node.right = construct(preOrder, inOrder, ps+index-is+1, pe, index+1, ie); return node; } public static void print(BinaryTreeNode node) { if(node != null){ print(node.left); System.out.println(node.value+" "); print(node.right); } } public static void main(String []args) { int[] preOrder = {1,2,4,7,3,5,6,8}; int[] inOrder = {4,7,2,1,5,3,8,6}; MianShiTi_6 test = new MianShiTi_6(); BinaryTreeNode node = reConstruct(preOrder, inOrder); print(node); }}新闻热点
疑难解答
