重建二叉树 及遍历

题目描述

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

剑指offer第63页

//首先建立一个二叉树类
/**
 * 二叉树定义
 *  tree.left 左节点
 *  tree.right 右节点
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

//solution类，实现重建二叉树
public class Solution {
    //主功能函数
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || in == null){
            return null;
        }
        TreeNode mm = reConstructBinaryTreeCore(pre, in, 0, pre.length-1, 0, in.length-1);
        return mm;
    }
    //核心递归
    public static TreeNode reConstructBinaryTreeCore(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {

        /**
         * 把前序遍历的值赋给二叉树的根节点
         *  tree.left 左节点
         *  tree.right 右节点
         */
        TreeNode tree = new TreeNode(pre[preStart]);
        tree.left = null;
        tree.right = null;
/**
 * preStart，preEnd为数组的索引
 * pre[preStart]，获取该二叉树的前序遍历节点的值
 *
 */
        if (preStart == preEnd && inStart == inEnd) {//如果(preStart == preEnd，说明树只有一个元素，该元素就是树唯一的元素
            return tree;
        }
        int root = 0;

        //<editor-fold desc="对中序in[]数组遍历得到分支">
        /**
         * 由二叉树的性质
         * 由前序遍历的值pre_i来确定根节点
         * 遍历中序遍历的值，寻找中序遍历中的根节点pre_j
         * 当中序遍历的值in_j==pre_i时，可以确定该根节点的左右子树
         */
        //</editor-fold>
        for(root= inStart; root < inEnd; root++){
            if (pre[preStart] == in[root]) {
                break;
            }
        }

        //<editor-fold desc="根节点为tree，对左右分支分别使用前序和中序遍历进行描述并分组，对分组使用核心递归方法，得到tree.left
        // 和tree.right
        // 然后依次得到tree.left的左右节点....">
        /**
         * 得到中序遍历的节点的值
         * leifLength 左子树的元素个数（不含根节点）
         * rightLength 右子树的元素个数（不含根节点）
         */
        //</editor-fold>
        int leifLength = root - inStart;
        int rightLength = inEnd - root;
        if (leifLength > 0) {
            //得到左节点的值
            tree.left = reConstructBinaryTreeCore(pre, in, preStart+1, preStart+leifLength, inStart, root-1);
        }
        if (rightLength > 0) {
            //得到右节点的值
            //下一层递归，则会得到tree.right的左或右节点......
            tree.right = reConstructBinaryTreeCore(pre, in, preStart+1+leifLength, preEnd, root+1, inEnd);
        }
        return tree;
    }


    //<editor-fold desc="遍历测试">
   /* //将二叉树先序遍历，用于测试结果
    public static void preTraverseBinTree(TreeNode node){
        if (node==null) {
            return;
        }
        System.out.print(node.val+",");
        if (node.left!=null) {
            preTraverseBinTree(node.left);
        }
        if(node.right!=null){
            preTraverseBinTree(node.right);
        }
    }
    //将二叉树中序遍历，用于测试结果
    public static void inTraverseBinTree(TreeNode node){
        if (node==null) {
            return;
        }
        if (node.left!=null) {
            inTraverseBinTree(node.left);
        }
        System.out.print(node.val+",");
        if(node.right!=null){
            inTraverseBinTree(node.right);
        }
    }
    */
    //</editor-fold>

    //将二叉树后序遍历，用于测试结果
    public static void postTraverseBinTree(TreeNode node){
        if (node==null) {
            return;
        }
        if (node.left!=null) {
            postTraverseBinTree(node.left);
        }
        if(node.right!=null){
            postTraverseBinTree(node.right);
        }
        System.out.print(node.val+",");
    }

    //主函数，用于测试结果
    public static void main(String[] args){
        int pre[] = {1,2,4,7,3,5,8,9,6};
        int in[]  = {4,7,2,1,8,5,9,3,6};
        TreeNode tree = reConstructBinaryTree(pre, in);

        //<editor-fold desc="测试">
       /* System.out.print("先序遍历结果:  {");
        preTraverseBinTree(tree);
        System.out.println("}");
        System.out.print("中序遍历结果:  {");
        inTraverseBinTree(tree);
        System.out.println("}");*/
        //</editor-fold>

        System.out.print("后序遍历结果:  {");
        postTraverseBinTree(tree);
        System.out.println("}");
    }
}

代码较长，可以先简要分析一下：

1）建立一个二叉树类

//首先建立一个二叉树类
/**
 * 二叉树定义
 *  tree.left 左节点
 *  tree.right 右节点
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

 思路：

a、根据前序遍历的数组第一个元素为根节点pre_i，在中序遍历数组中找到元素in_j=pre_i；设tree=pre_i

       for(root= inStart; root < inEnd; root++){
            if (pre[preStart] == in[root]) {
                break;
            }
        }

b、由中序遍历的思想，pre_i为根节点，可以将二叉树分为左右子树，所以pre_j左边的元素为左子树中的元素，集合为{L}，pre_j右边的元素为右子树中的元素,集合为{R}（此时具体组合未知）；

     int leifLength = root - inStart;
        int rightLength = inEnd - root;
        if (leifLength > 0) {
            //得到左节点的值
            tree.left = reConstructBinaryTreeCore(pre, in, preStart+1, preStart+leifLength, inStart, root-1);
        }
        if (rightLength > 0) {
            //得到右节点的值
            //下一层递归，则会得到tree.right的左或右节点......
            tree.right = reConstructBinaryTreeCore(pre, in, preStart+1+leifLength, preEnd, root+1, inEnd);
        }

c、根据前序遍历的思想，一定是先根节点，然后遍历左子树 (集合等于{L1}) ,再遍历右子子树(集合等于{R1}). L与L1元素一致，但排序顺序不同

于是对L和L1，使用reConstructBinaryTreeCore（），由L第一个元素得到其子树的节点tree.left（为父节点），由R得到tree.right.   

根据父节点tree.left在L1中的位置，将子树进行划分，得到下一级的节点（tree.left）.left  和（tree.left）.right;

同理，得到（tree.right）.left  和（tree.right）.right;

d、一直下去，得到最后的左右节点  这样树TreeNode就构建完成，由形如 tree.left or right这样的形式构成  

如图