剑指Offer第七题(Java实现)

题目：输入某二叉树的前序遍历和中序遍历结果，请重建该二叉树。假设输入的前序和中序的结果中都不含重复的数字。例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出他的头结点。二叉树结点的定义如下 struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLetf; BinaryTreeNode* m_Rigth; };

二叉树的结点类 package Ds;

public class BinaryNode { public T data; public BinaryNode left,right;

public BinaryNode(T data,BinaryNode<T>left,BinaryNode<T>right){ this.data=data; this.left=left; this.right=right; } public BinaryNode(){ } public BinaryNode(T data){ this(data, null, null); } public String toString(){ return this.data.toString(); } public boolean isLeaf(){ return this.left==null&&this.right==null; }

}

实现代码：

import java.util.Scanner; import Ds.BinaryNode; public class Test_07 { public static void main(String args[]) throws Exception{ Scanner scan=new Scanner(System.in); System.out.print("请输入前序序列:"); String preStr=scan.nextLine(); System.out.print("请输入中序序列:"); String inStr=scan.nextLine(); String[] preOrder=preStr.split(","); String[] inOrder=inStr.split(","); int preLength=preOrder.length; int inLength=inOrder.length; BinaryNode<String>root=construct(preOrder,inOrder,preLength,inLength); if(root!=null) { System.out.print("前序序列为:"); preOrderTraverse(root); } else System.out.println("The tree is empty"); if(root!=null) { System.out.print("中序序列为:"); inOrderTraverse(root); } else System.out.println("The tree is empty"); if(root!=null) { System.out.print("后序序列为:"); postOrderTraverse(root); } else System.out.println("The tree is empty"); } public static BinaryNode<String> construct(String[] preorder,String[] inorder,int preLength,int inLength) throws Exception{ if(preorder==null||inorder==null||preLength<=0||inLength<=0||preLength!=inLength) return null; return contructCore(preorder,0,preLength-1,inorder,0,inLength-1); } public static BinaryNode<String> contructCore(String[] preorder, int startPreorder,int endPreorder, String[] inorder, int startInorder,int endInorder) throws Exception { String rootValue=preorder[startPreorder]; BinaryNode<String>root=new BinaryNode<String>(); root.data=rootValue; root.left=null; root.right=null; if(startPreorder==endPreorder){ if(startInorder==endInorder&&preorder[startPreorder].equals(inorder[startInorder])){ return root; }else throw new Exception("Invalid input"); } int rootInorder=startInorder; while(rootInorder<=endInorder&&!inorder[rootInorder].equals(rootValue)) ++rootInorder; if(rootInorder==endInorder&&!inorder[rootInorder].equals(rootValue)) throw new Exception("Invalid input"); int leftLength=rootInorder-startInorder; int leftPreorderEnd=startPreorder+leftLength; if(leftLength>0){ root.left=contructCore(preorder,startPreorder+1,leftPreorderEnd,inorder,startInorder,rootInorder-1); } if(leftLength<endPreorder-startPreorder){ root.right=contructCore(preorder,leftPreorderEnd+1,endPreorder,inorder,rootInorder+1,endInorder); } return root; } //先序递归 public static void preOrderTraverse(BinaryNode<String> p){ if(p!=null){ System.out.print(p.data.toString()+" "); preOrderTraverse(p.left); preOrderTraverse(p.right); } } //中序递归 public static void inOrderTraverse(BinaryNode<String>p){ if(p!=null){ inOrderTraverse(p.left); System.out.print(p.data.toString()+" "); inOrderTraverse(p.right); } } //后序递归 public static void postOrderTraverse(BinaryNode<String>p){ if(p!=null){ postOrderTraverse(p.left); postOrderTraverse(p.right); System.out.print(p.data.toString()+" "); } } }

运行结果：