重建二叉树

问题描述

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

思路分析

由前序遍历很容易知道根结点是1，然后根据中序遍历知道左子树包含节点是4、7、2,右子树结点是5、3、8、6;又由前序遍历为2,4,7知道2是这三个节点的根结点，又中序为4,7,2知道4是2的左孩子，7是4的右孩子，右子树同理可判断

码上有戏

public class ConstructBinaryTree {

	public class TreeNode{
		int data;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int data){
			this.data=data;
		}
	}
	
	public TreeNode reConstructBinaryTree(int[] pre,int[] in){
		TreeNode root=constructCore(pre,0,pre.length-1,in,0,in.length-1);
		return root;
	}
	
	private TreeNode constructCore(int[] pre,int startPreOrder,int endPreOrder,int[] in,int startInOrder,int endInOrder)
	{
		//根据前序遍历找到根结点的值
		int rootValue=pre[startPreOrder];
		TreeNode rootNode=new TreeNode(rootValue);
		rootNode.left=null;
		rootNode.right=null;
		
		//只有一个结点，那么该节点就是根结点，直接返回
		if(startPreOrder==endPreOrder){
			if(startInOrder==endInOrder&&pre[startPreOrder]==in[startInOrder]){
				return rootNode;
			}
		}
		//根据中序遍历的结果找到根结点
		int rootOfInOrder=startInOrder;
		while(rootOfInOrder<=endInOrder&&in[rootOfInOrder]!=rootValue){
			rootOfInOrder++;
		}
		
		//异常处理
		if(rootOfInOrder==endInOrder&&in[rootOfInOrder]!=rootValue){
			return null;
		}
		
		//计算左子树的长度
		int leftSubTreeLen=rootOfInOrder-startInOrder;
		//根据左子树的长度计算前序的遍历结果中左子树的最后一个结点的下标
		int leftIndexOfPreOrderEnd=startPreOrder+leftSubTreeLen;
		//重建左子树
		if(leftSubTreeLen>0){
			rootNode.left=constructCore(pre,startPreOrder+1,leftIndexOfPreOrderEnd,in,startInOrder,rootOfInOrder-1);	
		}
		//重接右子树
		if(leftSubTreeLen<endPreOrder-startPreOrder){
			rootNode.right=constructCore(pre,leftIndexOfPreOrderEnd+1,endPreOrder,in,rootOfInOrder+1,endInOrder);		
		}
		return rootNode;
	}
	
	public void outTraver(TreeNode root){
		if(root!=null){
		outTraver(root.left);
		outTraver(root.right);
		System.out.print(root.data+" ");
		}
	}
	
	public static void main(String[] args) {
		int[] pre={1,2,4,7,3,5,6,8};
		int[] in={4,7,2,1,5,3,8,6};
		TreeNode root=new ConstructBinaryTree().reConstructBinaryTree(pre, in);
		new ConstructBinaryTree().outTraver(root);

	}

}

最后拿到根结点然后输出后续遍历如下

7 4 2 5 8 6 3 1