剑指offer之重建二叉树(图解)

题目源自：牛客网的剑指offer专题
题目地址：重建二叉树

题目描述

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

知识储备

懂得什么是二叉树、二叉树的前序中序后序遍历、以及如何确定唯一的二叉树？

二叉树：每个结点最多有两个子树(即左子树和右子树)的树结构。
前序遍历(根左右)：先访问根节点，再依次遍历左子树和右子树。
中序遍历(左根右)：先遍历左子树，然后访问根节点，再遍历右子树。
后序遍历(左右根)：先遍历左子树，再遍历右子树，最后访问根节点。
如何确定唯一的二叉树：已知中序遍历序列和前序/后序遍历序列。

如果你对二叉树的相关知识比较模糊，赶紧去补充学习一下：深入学习二叉树(一) 二叉树基础

参考思路

1.根据前序遍历序列确定根结点root=pre[startPre]。
2.在中序遍历序列中找到根结点的位置i，根结点的左右即为左右子树的中序遍历序列。
3.根据左子树的中序遍历序列确定左子树的结点个数(i-startIn)，从而得到左右子树的前序遍历序列。
4.利用左右子树的前序和中序遍历序列重复步骤1-3，递归建立二叉树，最后返回根结点root即可。
注意：当startPre>endPre||startIn>endIn时返回null。
二叉树根结点的图解过程，

根结点左子树的图解过程，

根结点右子树的图解过程，

重建的二叉树，

参考代码

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=buildTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    public TreeNode buildTree(int []pre,int startPre,int endPre,int []in,int startIn,int endIn){
        if(startPre>endPre||startIn>endIn){
            return null;
        }
        //前序遍历先访问根结点，所以前序遍历序列的首个元素即为根结点。
        TreeNode root=new TreeNode(pre[startPre]);
        //在中序遍历序列中寻找根节点的位置，并将序列分为左右子树
        for(int i=startIn;i<=endIn;i++){
            if(in[i]==pre[startPre]){
                int leftcount=i-startIn;//求左子树结点个数
                //在左子树序列中寻找根的左孩子结点
                root.left = buildTree(pre,startPre+1,startPre+leftcount,in,startIn,i-1);
                //在右子树序列中寻找根的右孩子结点
                root.right = buildTree(pre,startPre+leftcount+1,endPre,in,i+1,endIn);
                break;
            }
        }
        return root;
    }
}