剑*offer04 重建二叉树

题目描述

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

题解

先序遍历就是先输出root节点在左节点再右节点，中序遍历就是先左再root最后右节点

根据先序遍历，我们可以知道这棵树的root节点，即root = pre[0],再去中序遍历中找到root节点，中序遍历中root节点左边的即为左子树，右边的即为右子树。

1. 先序 1 2 4 7 3 5 6 8 ->root节点1
   中序 4，7，2，1，5，3，8，6
   左子树 右子树
   所以在先序中可以得到
   1 2 4 7 3 5 6 8->2 4 7为左子树，5 6 8为右子树
2. 递归 把左右子树分别看成一棵树，root.left = reConstructBinaryTree(pr,ino);
   root.right = reConstructBinaryTree(pr,ino);
   当然，如果先序中序没有数了，就说明这个root节点的左/右节点为空了。
3. 返回root节点。

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Solution {
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    
        TreeNode root = new TreeNode(pre[0]);
        int length = pre.length;
        if(length==1){
    
            root.left = null;
            root.right = null;
            return root;
        }
        int location=0;
        for(int i = 0;i<in.length;i++){
    
            if(root.val == in[i]){
    
                location = i;
            }
        }
        
        if(location>0){
    
            int[] pr = new int[location];
            int[] ino = new int[location];
            for(int j =0;j<location;j++){
    
                pr[j]=pre[j+1];
                ino[j]=in[j];
            }
            root.left=reConstructBinaryTree(pr,ino);
        }else{
    root.left =null;}
        if(length-location-1>0){
    
		int[] pr=new int[length-location-1];
		int[] ino=new int[length-location-1];
		for(int j=location+1;j<length;j++){
    
			ino[j-location-1]=in[j];
			pr[j-location-1]=pre[j];
		}
		root.right=reConstructBinaryTree(pr,ino);
	}else{
    
		root.right=null;
	}
	
	
    return root;
    }
    
    
}