题目描述

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

解题思路一

通过递归构造二叉树，首先通过先序遍历找到根节点，然后以根节点为基准，通过中序遍历序列和先序序列找出左子树的先序序列和中序序列以及右子树的对应序列，再递归进行构造左右子树。

public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    int length = pre.length - 1;
    return reConstruct(pre, in, 0, length, 0, length);
}

public static TreeNode reConstruct(int[] pre, int[] in, int left1, int right1, int left2, int right2) {
    TreeNode node;
    if (left1 == right1) {
        //只剩一个结点，直接新建一棵树，当前元素作为根节点返回
        node = new TreeNode(pre[left1]);
        node.left = null;
        node.right = null;
        return node;
    } else if (left1 > right1) {
        //pre没有数
        return null;
    } else {
        //pre有多个数字
        //第一个元素为当前树的根节点
        node = new TreeNode(pre[left1]);
        //获取根节点在中序遍历的下标
        int middle = search(in, pre[left1], left2, right2);
        //重新构建左子树的前序、中序数组
        //左子树的结点长度
        node.left = reConstruct(pre, in, left1 + 1, middle - left2 + left1, left2, middle - 1);
        //重新构建右子树的前序、中序数组
        node.right = reConstruct(pre, in, left1 + middle - left2 + 1, right1, middle + 1, right2);
        return node;
    }
}


public static int search(int[] array, int target, int left, int right) {
    //找出target的下标位置
    for (int i = left; i <= right; i++) {
        if(array[i] == target)
            return i;
    }
    return -1;
}

改进版

public class Solution {

   public  TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        } else {
            //构造树的根节点
            TreeNode root = new TreeNode(pre[0]);
            root.left = null;
            root.right = null;
            int middle = search(in, pre[0]);
            if(middle != -1){
                //构造左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, middle +1), Arrays.copyOfRange(in, 0, middle));
                //构造右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, middle+1, pre.length), Arrays.copyOfRange(in,middle+1, in.length));
            }
            return root;
        }
    }
    public  int search(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if(array[i] == target)
                return i;
        }
        return -1;
    }
    
}