剑指offer #4 重建二叉树

剑指offer 题集 https://www.jianshu.com/nb/32116527

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

二叉树的前序、中序、后序遍历：二叉树的遍历中的“前”、“中”、“后”，指的就是二叉树中的父节点的顺序。
举个例子：

二叉树

前序遍历(先序遍历)：
前序遍历就是先遍历父节点，再遍历左子树，最后遍历右子树。左子树或者右子树也按照这个规则遍历。如上图的二叉树所示：
1、先遍历整棵树的父节点，也就是F。
2、然后再遍历左子树。左子树也先遍历父节点，就是C。
3、再遍历C节点的左子树，其父节点是A。
4、A节点没有子节点，即C节点的左子树已经遍历完成。接下去就是遍历C节点的右子树。就是D、B。
5、C节点的左右子树已经全部完成了，也就是F的左子树遍历已经完成。接下去遍历F的右子树，即：E、H、G、M。
6、上述二叉树的前序遍历为：F、C、A、D、B、E、H、G、M。

解题思路：题目中告诉我们二叉树的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。分析过程如下：
1、前序遍历的第一个点就是根节点，所以二叉树的根节点是“1”；
2、中序遍历是先遍历左子树，再根节点，后右节点。所以在中序遍历，在“1”前边的是左子树，在“1”后边的是右子树。所以该题中，“4”、“7”、“2”是左子树。
3、前序遍历的第二个节点，就是左子树的父节点。所以在中序遍历中，在"2"前面的均是左子树。在该题中节点“2”，没有右子树。
4、以此类推可重建二叉树。

代码如下：

//pre为前序遍历序列，in为中序遍历序列
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }
    public TreeNode preIn(int[] p, int pi, int pj, int[] n, int ni, int nj, HashMap<Integer, Integer> map) {
        if (pi > pj) {
            return null;
        }
        TreeNode head = new TreeNode(p[pi]);
        int index = map.get(p[pi]);
        head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);
        head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
        return head;
    }