根据先序遍历和中序遍历恢复出二叉树

class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;
	
	public HeroNode(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
}

public class BinaryTree {
	private HeroNode root;
	
	public void setRoot(HeroNode root) {
		this.root = root;
	}
	public HeroNode getRoot() {
		return root;
	}
    //根据先序遍历和中序遍历序列恢复二叉树
	public  HeroNode rebuildBinaryTree(ArrayList<HeroNode> preod, int preOrderStart, int preOrderEnd, ArrayList<HeroNode> inod, int inOrderStart, int inOrderEnd) {
		if(preOrderStart>preOrderEnd||inOrderStart>inOrderEnd) {
			return null;
		}
		HeroNode root=preod.get(preOrderStart);
		for(int i=inOrderStart;i<=inOrderEnd;i++) {
			if(inod.get(i).getNo()==root.getNo()) {
				root.setLeft(rebuildBinaryTree(preod, preOrderStart+1, preOrderStart+(i-inOrderStart), inod, inOrderStart, i-1));
				root.setRight(rebuildBinaryTree(preod, preOrderStart+(i-inOrderStart)+1, preOrderEnd, inod, i+1, inOrderEnd));
				//return root;
			}
		}
		return root;
	}
}

public class BinaryTreeDemo {

	public static void main(String[] args) {
		//先定义一棵树
		BinaryTree binaryTree=new BinaryTree();
		
		//定义所有的子孙节点
		HeroNode root=new HeroNode(1,"宋江");
		HeroNode root1=new HeroNode(2, "吴用");
		HeroNode root2=new HeroNode(3, "卢俊义");
		HeroNode root3=new HeroNode(4, "林冲");
        
        //测试：根据先序序列和中序序列恢复二叉树
		//先序遍历序列
		ArrayList<HeroNode> preod=new ArrayList<HeroNode>();
		preod.add(root);
		preod.add(root1);
		preod.add(root2);
		preod.add(root3);
		//后续遍历序列
		ArrayList<HeroNode> inod=new ArrayList<HeroNode>();
		inod.add(root1);
		inod.add(root);
		inod.add(root2);
		inod.add(root3);
		
		binaryTree.setRoot(binaryTree.rebuildBinaryTree(preod, 0, preod.size()-1, inod, 0, inod.size()-1));
        
        //测试结果
          System.out.println("前序遍历");//1 2 3 4 
		  binaryTree.preOrder();
		  
		  System.out.println("中序遍历");//2 1 3 4 
		  binaryTree.inOrder();
		  
		  System.out.println("后序遍历");//2 4 3 1 
		  binaryTree.postOrder();
    }
}