根据二叉树的先根序和中根序遍历二叉树

对于计算机专业的学生和从事代码行业的认识来说，二叉树这种数据结构可谓是耳熟能详了，时常温习数据结构没有什么坏处的事。

对于左边这张图来说他的

先根序遍历：ABDHECFG

中根序遍历：HDBEAFCG

后根序遍历：HDEBFGCA

知道图的时候想知道先根序中根序后根序遍历就是套概念的事。那如果对于知道遍历排序怎么恢复成原来的二叉树呢？在这里我就用知道先根序遍历和中根序遍历求图写一下。

首先我们对二叉树每一个节点定义一个数据类型

class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
}

有了数据结构之后我们就可以去写转换的方法了，在java中其实有个最简洁的解决办法就是

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
       if(pre.length == 0||in.length == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            if(pre[0] == in[i]){
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
            }
        }
        return node;
    }

上面这个是代码上比较方便的解法了，核心就一句，递归调用就可以了。但是对于初学可能看起来比较困难写了，我写了个复杂版的，但是相对的代码拆分的就比较细，看起来比较好理解了。

public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length <= 0) {
            return null;
        }
        int gen = pre[0];
        List<Integer> leftListTree = new ArrayList<>();//左子树中根
        List<Integer> rightListTree = new ArrayList<>();//右子树中根
        boolean startRight = false;
        for (int i = 0; i < pre.length; i++) {
            if (gen == in[i]) {
                startRight = true;
                continue;
            }
            if (!startRight) {
                leftListTree.add(in[i]);
            } else {
                rightListTree.add(in[i]);
            }
        }
        List<Integer> leftListTreeQian = new ArrayList<>();//左子树前根
        List<Integer> rightListTreeQian = new ArrayList<>();//右子树前根
        for (int i = 1; i < in.length; i++) {
            if (i <= leftListTree.size()) {
                leftListTreeQian.add(pre[i]);
            } else {
                rightListTreeQian.add(pre[i]);
            }
        }
        TreeNode treNode = new TreeNode(gen);
        treNode.left = reConstructBinaryTree(listToArray(leftListTreeQian), listToArray(leftListTree));
        treNode.right = reConstructBinaryTree(listToArray(rightListTreeQian), listToArray(rightListTree));
        return treNode;
    }

因为我在代码中间使用的是list，而方法传递的参数是数组的原因，所以有个list转数组的方法

public static int[] listToArray(List<Integer> list) {
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }
        return array;
    }

代码都是很简单的代码，看懂的话也是比较简单。