前言

这个怎么说呢，如果你想看本篇博文的话，我的个人建议是先熟练掌握如何使用中序+先序、后序 创建一颗二叉树的手写过程。因为这个暴力过程的话其实还是一个DFS的过程，说白了就是一直找，找到根节点，然后通过在去建树，直到叶子节点，然后叶子节点找不到下面的节点了直接退出，或者是根据那个排序的寻找的下标（具体看代码），难度其实不难，而且这个代码很能体现分治思想。这里的话为了便于理解，我就不写优化后的代码了，优化的话也很简单，无非是几个参数的优化，优化地址空间。
这个还是很好写的，但是不好理解。

我这里本来是想要搞几个图来演示的，但是不好搞，都在代码里，自己debug去吧。

这个所谓的树形暴力呢，其实和先前的那种通过HashMap去搜索图的联通节点的很像，区别就是这里维护了两个数组，通过数组去找对应的节点，所以理论上，我们完全可以先优化一下存储结构，直接使用HashMap来存储两个排序，然后去找。不过这里的话为了便于理解还是使用通用的。

节点表示

这里还是直接使用内部类

    static class Node{
    
        Node right;
        Node left;
        Character value;

        public Node(Character value) {
    
            this.value = value;
        }

    }

后序+中序建树

我们先来看看核心代码好吧。

    public static Node BuildTreeByHou(char[] BeforeOrder,char[] InnerOrder){
    
        if(BeforeOrder.length==0){
    
            //此时说明不存在那个根节点了，已经走到底了
            return null;
        }
        //调用入口，可以忽略
        //创建根节点，后序遍历最后一个就是根节点（代码请先看这里，这里才是核心！）
        char Root_Value = BeforeOrder[BeforeOrder.length-1];
        Node Root = new Node(Root_Value);
        //我们先创建左子树，所以此时，划分的左子树就相当于一个完整的树
        //这里开始体现分治思想,左子树的个数就是那个根节点所在的小标大小
        int left_tree_length = find(InnerOrder,Root_Value);
        //开始划分
        //3、切出左子树的中序和后序
        char[] leftInnerOrder = Arrays.copyOfRange(InnerOrder, 0, left_tree_length);
        char[] leftBeforeOrder = Arrays.copyOfRange(BeforeOrder, 0, left_tree_length);
        Root.left = BuildTreeByHou(leftBeforeOrder,leftInnerOrder);


        //4、切出右子树的中序和后序
        //左子树是0-left_tree_length 那么剩下的自然就是右子树的，但是后序遍历，此时是把后序的最后一个用完了，所以不要了
        char[] rightInnerOrder = Arrays.copyOfRange(InnerOrder, left_tree_length+1, InnerOrder.length);
        char[] rightBeforeOrder = Arrays.copyOfRange(BeforeOrder, left_tree_length, BeforeOrder.length-1);
        Root.right = BuildTreeByHou(rightBeforeOrder,rightInnerOrder);

        return Root;
    }

其实非常简单，由于中序是 左根右 的形式，所以你懂的，只要找到了 根节点，那么我们后面就可以找到它的左子树，右子树，而对于后序遍历而言，最后一个元素就是整个数的根节点，然后对于左右子树而言，又是一个相对完整的数，此时我们发现了一个可以重复的步骤。然后在对于左子树，或者右子树来说，找到里面的根节点又可以建立，那么它的左子树的根节点，或者右子树的，不就在左右子树对应的后序集合的最后一个嘛。
如图：

先序+中序建树

同样的，通过先序+中序建树也是一样的，不同之处其实就是在先序里面找根节点是第一个。

    public static Node BuildTreeByXian(char[] PreOrder,char[] InnerOrder){
    
        //这里的话我们同样地先去找到根节点,和后序的区别其实就是那个根节点的区别
        if (PreOrder.length==0){
    
            return null;
        }
        char Root_Value = PreOrder[0];
        Node Root = new Node(Root_Value);
        int left_tree_length = find(InnerOrder,Root_Value);

        char[] leftInnerOrder = Arrays.copyOfRange(InnerOrder, 0, left_tree_length);
        char[] leftPreOrder = Arrays.copyOfRange(PreOrder, 1, left_tree_length+1);
        Root.left = BuildTreeByXian(leftPreOrder,leftInnerOrder);


        //4、切出右子树的中序和后序
        //此时的左子树是不一样的了
        char[] rightInnerOrder = Arrays.copyOfRange(InnerOrder, left_tree_length+1, InnerOrder.length);
        char[] rightPreOrder = Arrays.copyOfRange(PreOrder, left_tree_length+1, PreOrder.length);
        Root.right = BuildTreeByXian(rightPreOrder,rightInnerOrder);
        return Root;
    }

完整代码

package com.huterox.LevelTest2;

/** * A * B E * C * D */

import java.util.Arrays;

public class MyBuildTree {
    
    static class Node{
    
        Node right;
        Node left;
        int value;

        public Node(int value) {
    
            this.value = value;
        }

    }

    public static int find(char[] arr,int value){
    
// 这个主要是用来找那个根节点的下标的
        for (int i = 0; i < arr.length; i++) {
    
            if (arr[i] == value) {
    
                return i;
            }
        }
        return -1;
    }



    public static Node BuildTreeByHou(char[] BeforeOrder,char[] InnerOrder){
    
        if(BeforeOrder.length==0){
    
            //此时说明不存在那个根节点了，已经走到底了
            return null;
        }
        //调用入口，可以忽略
        //创建根节点，后序遍历最后一个就是根节点（代码请先看这里，这里才是核心！）
        char Root_Value = BeforeOrder[BeforeOrder.length-1];
        Node Root = new Node(Root_Value);
        //我们先创建左子树，所以此时，划分的左子树就相当于一个完整的树
        //这里开始体现分治思想,左子树的个数就是那个根节点所在的小标大小
        int left_tree_length = find(InnerOrder,Root_Value);
        //开始划分
        //3、切出左子树的中序和后序
        char[] leftInnerOrder = Arrays.copyOfRange(InnerOrder, 0, left_tree_length);
        char[] leftBeforeOrder = Arrays.copyOfRange(BeforeOrder, 0, left_tree_length);
        Root.left = BuildTreeByHou(leftBeforeOrder,leftInnerOrder);


        //4、切出右子树的中序和后序
        //左子树是0-left_tree_length 那么剩下的自然就是右子树的，但是后序遍历，此时是把后序的最后一个用完了，所以不要了
        char[] rightInnerOrder = Arrays.copyOfRange(InnerOrder, left_tree_length+1, InnerOrder.length);
        char[] rightBeforeOrder = Arrays.copyOfRange(BeforeOrder, left_tree_length, BeforeOrder.length-1);
        Root.right = BuildTreeByHou(rightBeforeOrder,rightInnerOrder);

        return Root;
    }

    public static Node BuildTreeByXian(char[] PreOrder,char[] InnerOrder){
    
        //这里的话我们同样地先去找到根节点,和后序的区别其实就是那个根节点的区别
        if (PreOrder.length==0){
    
            return null;
        }
        char Root_Value = PreOrder[0];
        Node Root = new Node(Root_Value);
        int left_tree_length = find(InnerOrder,Root_Value);

        char[] leftInnerOrder = Arrays.copyOfRange(InnerOrder, 0, left_tree_length);
        char[] leftPreOrder = Arrays.copyOfRange(PreOrder, 1, left_tree_length+1);
        Root.left = BuildTreeByXian(leftPreOrder,leftInnerOrder);


        //4、切出右子树的中序和后序
        //此时的左子树是不一样的了
        char[] rightInnerOrder = Arrays.copyOfRange(InnerOrder, left_tree_length+1, InnerOrder.length);
        char[] rightPreOrder = Arrays.copyOfRange(PreOrder, left_tree_length+1, PreOrder.length);
        Root.right = BuildTreeByXian(rightPreOrder,rightInnerOrder);
        return Root;
    }


    public static void main(String[] args) {
    
        char[] PreOrder = new char[]{
    'A','B','C','D','E'};
        char[] InnerOrder = new char[]{
    'C', 'D', 'B', 'A', 'E'};
        char[] BeforeOrder = new char[]{
    'D', 'C', 'B', 'E', 'A'};
// Node root = BuildTreeByHou(BeforeOrder,InnerOrder);
        Node root = BuildTreeByXian(PreOrder,InnerOrder);

        System.out.println("创建成功");
    }
}