剑指offer（四）重建二叉树

写在前面：

为了增长一下自己的数据结构能力，也为了面试准备，准备将剑指Offer做一下，并与各位分享，希望各位可以对代码以及思路提提建议，欢迎志同道合者，谢谢。

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

思路：

首先讲一下什么是二叉树的中序，前序，后序遍历，大家也可以看看我这篇二叉树相关,中序，前序，后序，遍历，大家只需要记住这个是相对于根节点的就好，左子树和右子树的顺序不变，比如说前序遍历，也就是先打印根节点，然后打印左子树然后是右子树，中序就是先打印左子树，然后打印根节点，然后打印右子树，那么后序想必大家都知道了吧，左子树，右子树，根节点，

好了，知道了什么是前序，中序，后序，，那么我们看看这三种排序有啥特点呢，前序已经说了，先打印根节点，也就是前序按顺序来，都是根节点，那么中序呢，先打印左子树，然后打印根节点，那么我们能不能根据前序的根节点在中序中找到他的左子树呢，还有右子树，举个栗子

前序 1,2,4,7,3,5,6,8
中序 4,7,2,1,5,3,8,6

首先1是根节点，那么中序中1的左边(4,7,2)全是1的左子树的节点，右边(5,3,8,6)全都是右子树节点，然后我们看左子树，根节点是2，中序中2的左边(4,7)都是2的左子树节点，2的右边没有数据，说明他没有右子树，依次类推,

注意，每次找到根节点之后，那么就将中序从根节点分为两部分，左边是左子树，右边是右子树，然后分别进行递归，

好了，现在正式进入代码环节

package com.itzmn.offer;


import javax.swing.tree.TreeNode;

/**
 * @Auther: 张梦楠
 * @Date: 2018/7/28 08:12
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  重建二叉树
 *
 *   输入前序与中序，还原出二叉树，
 *
 *   前序的每一个都是根节点，根据根节点在中序中寻找，左边的就是左子树的节点，右边的就右子树的节点
 *
 */
public class Offer4 {

    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 treeNode = new Offer4().reConstructBinaryTree(pre, in);

        new Offer4().printpreTree(treeNode);
    }



    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {

        if (pre.length == 0 || in.length == 0 || pre.length != in.length){
            System.out.println("您输入的数据不合法");
            return null;
        }


        return createBinaryTree(pre,0,pre.length-1,in , 0 , in.length-1);
    }

    /**
     *
     * @param pre  前序遍历
     * @param preB  前序遍历开始的坐标
     * @param preE  前序遍历最终坐标
     * @param in  中序遍历
     * @param inB  中序遍历开始位置
     * @param inE  中序遍历结束位置
     * @return   返回二叉树根节点
     */
    private TreeNode createBinaryTree(int[] pre, int preB, int preE, int[] in, int inB, int inE) {


        if (preB >preE){
            return null;
        }

        /**
         *  从前序遍历中寻找根节点
         *  根据根节点在中序遍历中找到左右子树
         */
        //这是根节点的值，
        int value = pre[preB];

        int index = inB;

        // 在中序遍历中找到这个根节点
        while (index <= inE && in[index] != value){
            index++;
        }
        // 判断中序中是否有这个根节点

        if (index > inE){
           throw new RuntimeException("输入的数据有问题");
        }


        TreeNode treeNode = new TreeNode(value);

        /**
         *  构建左子树
         */
        treeNode.left = createBinaryTree(pre,preB+1,preB+index-inB,in,inB,index-1);

        treeNode.right = createBinaryTree(pre,preB+index-inB+1,preE,in,index+1,inE);
        return treeNode;
    }


    /**
     *  输出数的前序遍历
     * @param treeNode
     */
    public void printpreTree(TreeNode treeNode){

        System.out.println(treeNode.val);
        if (treeNode.left != null){
            printpreTree(treeNode.left);
        }
        if (treeNode.right != null){
            printpreTree(treeNode.right);
        }

    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }

  }





}

希望大家可以多多指点，优化一下，
QQ群：552113611

最后编辑于：2018.07.28 09:56:10