对于二叉树，由前序遍历和中序遍历或中序遍历和后序遍历都可以还原二叉树，但是由前序遍历和后序遍历无法还原二叉树，因为无法确定左子树和右子树的位置。

根据前序遍历和中序遍历还原二叉树：

由前序遍历的第一个值可以确定根节点，再由中序遍历找到根节点的位置，其左边的为左子树，右边的为右子树。

再重构前序遍历结果和中序遍历结果，再递归上述过程即可完全还原二叉树。

在写代码前先简单介绍一下java中的System.arraycopy(Object src,
                             　　　　　　　　　　　　　　　　int srcPos,
                             　　　　　　　　　　　　　　　　Object dest,
                             　　　　　　　　　　　　　　　　int destPos,
                             　　　　　　　　　　　　　　　　int length)

其中：src表示源数组，srcPos表示源数组要复制的起始位置，desc表示目标数组，desPos表示目的数组复制的起始位置，length表示要复制的长度。

 

public class Solution {

    public  static TreeNode reConstructBinaryTree(int [] prev,int [] in) {
    //不管什么遍历方式，结果长度肯定是一样的，都是总结点数
        if(prev.length!= in.length || prev.length<1){
            return null;
        }
    //只有一个节点，那就是根节点
        if(prev.length == 1){
            return new TreeNode(prev[0]);
        }
    //在中序遍历结果中找根节点
        int index = -1;
        for(int i=0;i<in.length;i++){
            if(in[i]==prev[0]){
                index=i;
                break;
            }
        }
    //没找到，说明数据有问题
        if(index==-1){
            return null;
        }
    //找到根节点了
        TreeNode root = new TreeNode(prev[0]);
    //得到左子树的前序遍历结果
        int[] lChildPrev = new int[index];
        System.arraycopy(prev,1,lChildPrev,0,index);
    //得到左子树的中序遍历结果
        int[] lChildin = new int[index];
        System.arraycopy(in,0,lChildin,0,index);
    //通过递归，得到左子树结构
        root.left=reConstructBinaryTree(lChildPrev,lChildin);
        
    //得到右子树的前序遍历结果
        int[] rChildPrev = new int[in.length-1-index];
        System.arraycopy(prev,index+1,rChildPrev,0,in.length-1-index);
    //得到右子树的中序遍历结果
        int[] rChildin = new int[in.length-1-index];
        System.arraycopy(in,index+1,rChildin,0,in.length-1-index);
    //通过递归，得到右子树结构
        root.right=reConstructBinaryTree(rChildPrev,rChildin);
    //得到完整的二叉树结构
        return root;
    }

    //测试
    public static void main(String[] args){
    int[] prev = {1,2,4,7,3,5,6,8};
    int[] in = {4,7,2,1,5,3,8,6};
    TreeNode root = reConstructBinaryTree(prev,in);
    prevPrintTreeNode(root);
    System.out.println();
    inPrintTreeNode(root);
    }
//测试结果
//1 2 4 7 3 5 6 8 
//4 7 2 1 5 3 8 6

}

 

版权声明：本文为wenbinshen原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/wenbinshen/p/11213973.html