剑指offer - 重建二叉树(Java实现)

题目连接：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&&tqId=11157&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

• 下面首先我们呢来介绍如何根据二叉树的前序遍历和中序遍历来确定一颗二叉树。

前序遍历：[1,2,4,7,3,5,6,8]
中序遍历：[4,7,2,1,5,3,8,6]

  我们知道，前序遍历是先输出根结点，所以在一个数组中，出现的第一个数字必然是这个二叉树的根结点。对于一颗二叉树来说在进行中序遍历时，只有左子树上面所有的点按照中序遍历的规则都遍历结束了我们才输出根结点，然后在中序遍历其右子树上上面的所有点。所以对于中序遍历得到的数组来说，对于某一个位置的数值，其左边的数字都属于这棵树的左子树上面的点，其右边的数字都属于其右子树上面的点。如果我们知道了某一颗树的根节点，又知道其左右子树，那么我们就可以唯一的确定一颗二叉树。

• 图解重建二叉树

  看图我们可以发现，前序遍历得到的数组的第一个数字就是当前树的根节点，我们在中序遍历的数组中找到这个根结点，这个根节点的左边属于这棵树的左子树，右边属于这棵树的右子树，一直重复这样的过程就可以构造一颗二叉树出来。
  综上所述，我们可以使用递归的方式来构建这颗二叉树，以中序遍历的第一个值作为当前树的根结点，然后处理出左边的中序遍历结果，以及前序遍历结果，向左递归以同样的方式算下面的子树的情况。右边则使用同样的方式处理。如果最后我们得到了空的中序遍历结果或者空的前序遍历结果，说明我们到达了叶子节点的最后一层，此时我们就可以将这个条件作为递归的出口。

  思路一：自己编写函数来构建出新的中序遍历和前序遍历将结果，然后在这个基础上进行相关的判断与递归。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return build(pre, 0, pre.length - 1, in, 0, in.length - 1); //构建新的中序和前序遍历结果
    }
    TreeNode build(int[] pre, int preLeft, int preRight, int[] vin, int vinLeft, int vinRight) {
        if(preLeft > preRight || vinLeft > vinRight) return null;
        TreeNode root = new TreeNode(pre[preLeft]);
        for(int i = vinLeft; i <= vinRight; ++ i) {
            if(vin[i] == pre[preLeft]) {//中序遍历找到根结点
                root.left = build(pre, preLeft + 1, preRight + i - vinRight, vin, vinLeft, i - 1);//左边归左子树
                root.right = build(pre, preLeft + i - vinLeft + 1, preRight, vin, i + 1, vinRight);//右边归右子树
            }
        }
        return root;
    }
}

  思路二：使用库函数来构建新的中序和前序遍历结果，Arrays.copyOfRange(pre, s, e)表示将pre数组中的[s, e)位置的结果复制到一个新的数组中去。使用时需要导入 import java.util.*

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int len1 = pre.length, len2 = in.length;
        if(len1 == 0 || len2 == 0) { //数组为空说明到了叶子节点的下一层
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < len2; ++ i) {
            if(in[i] == pre[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));//左子树前序和中序结果
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, len1), Arrays.copyOfRange(in, i + 1, len2));//右子树前序和中序结果
            }
        }
        return root;
    }
}