重建二叉树.md

题目描述

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

二叉树的节点的定义如下：

/**
 * 二叉树节点
 * @Author rex
 * 2018/6/11
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

测试用例

• 普通二叉树（完全二叉树；不完全二叉树）
• 特殊二叉树（所有节点都没有右子节点的二叉树；所有节点都没有左子节点的二叉树；只有一个节点的二叉树）
• 特殊输入测试（二叉树的根节点为空；输入的前序序列和中序序列不匹配）

题目考点

• 考察应聘者对二叉树的前序遍历和中序遍历的理解程序。只有对二叉树的不同遍历算法有了深刻的理解，应聘者才有可能在遍历序列汇总划分出左、右子数对应的子序列。
• 考察应聘者分析复杂问题的能力。我们把构建二叉树的大问题分解成构建左、右子树的两个小问题。我们发现小问题和大问题在本质上是一致的，因此可以用递归的方式解决。

解题思路

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。接下来的事情我们就可以用 递归 的方法完成了。

自己解题

想到了方法，却写不出代码。

PS： 递归方法的参数需要多几轮来验证是否正确，不要想当然。

参考解题

/**
 * 重建二叉树
 * @Author rex
 * 2018/6/11
 */
public class Solution {

    /**
     * 利用map便于直接根据先序遍历的值定位到中序遍历的索引
     */
    private static Map<Integer, Integer> map = new HashMap<>();

    /**
     * @Author rex
     * @Date 2018/6/12 下午9:21
     * @Description 构建树
     * @param pre 先序遍历序列
     * @param in 后序遍历序列
     */
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return root;

    }

    /**
     * @Author rex
     * @Date 2018/6/12 下午9:20
     * @Description 递归建立树
     * @param pre 先序遍历序列
     * @param startPreIndex   子 先序遍历序列开始索引
     * @param endPreIndex  子 先序遍历序列结束索引
     * @param pre 后序遍历序列
     * @param startPreIndex   子 后序遍历序列开始索引
     * @param endPreIndex  子 后序遍历序列结束索引
     */
    private static TreeNode reConstructBinaryTree(int[] pre, int startPreIndex, int endPreIndex,
                                                  int[] in, int startInIndex, int endInIndex) {
        if (startPreIndex > endPreIndex) {
            return null;
        }
        int rootValue = pre[startPreIndex];
        TreeNode root = new TreeNode(rootValue);
        int rootValueIndex = map.get(rootValue);
        // 需要多验证几步确定参数(用相对个数来确定索引，先序遍历序列不要直接去使用中序遍历的索引)
        root.left = reConstructBinaryTree(pre, startPreIndex + 1, rootValueIndex - startInIndex + startPreIndex, in, startInIndex, rootValueIndex - 1);
        root.right = reConstructBinaryTree(pre, rootValueIndex - startInIndex + startPreIndex + 1, endPreIndex, in, rootValueIndex + 1, endInIndex);
        return root;
    }
}