4. 重建二叉树

4.1 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如：

前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8 ｝ 根、左、右

中序遍历序列｛ 4, 7, 2, 1, 5, 3, 8, 6 } 左、根、右

重建二叉树并输出它的头结点。

4.2 解题思路

• 由前序遍历的第一个节点可知根节点。
• 根据根节点，可以将中序遍历划分成左右子树。
• 在前序遍历中找出对应的左右子树，其第一个节点便是根节点的左右子节点。
• 按照上述方式递归便可重建二叉树。

4.3 实现代码

public class Test { 
    /** 
     * 二叉树节点类 
     */
    public static class BinaryTreeNode { 
        int value; 
        BinaryTreeNode left; //左节点
        BinaryTreeNode right; //右节点
    }
    
    /** 
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。  
     * @param preorder 前序遍历
     * @param inorder 中序遍历   //后序遍历 postorder
     * @return 树的根结点 
     */
    public static BinaryTreeNode construct(int[] preorder, int[] inorder) { 
        // 输入的合法性判断，两个数组都不能为空，并且都有数据，而且数据的数目相同
        if (preorder == null || inorder == null ||  //两个数组不能为空
            preorder.length != inorder.length || inorder.length < 1) { //长度要一样。长度不能为0  
            return null;
        } 
        return construct(preorder, 0, preorder.length - 1, 
                         inorder, 0, inorder.length - 1); //返回另一个重建方法
    }
    
    /** 
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
     * @param preorder 前序遍历
     * @param ps 前序遍历的开始位置
     * @param pe 前序遍历的结束位置
     * @param inorder 中序遍历 
     * @param is 中序遍历的开始位置 
     * @param ie 中序遍历的结束位置
     * @return 树的根结点 
     */
    public static BinaryTreeNode construct(int[] preorder, int ps, int pe,
                                           int[] inorder, int is, int ie) {
        /**步骤1：安全性判断**/ 
        // 开始位置大于结束位置说明已经没有需要处理的元素了 
        if (ps > pe) { 
            return null;
        } 
        
        /**步骤2：获取根节点在中序遍历的下标位置！**/
        // 取前序遍历的第一个数字，就是当前的根结点 
        int value = preorder[ps];  //根节点拿到手
        int index = is;  //拿到中序遍历的起始位置下标
        // 在中序遍历的数组中找根结点的位置 ，因为中序遍历是左根右，根节点所在位置是区分开左右子树的关键排序
        while (index <= ie && inorder[index] != value) {
            index++;
        }
        // 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常
        if (index > ie) {
            throw new RuntimeException("Invalid input");
        }
        
        /**步骤3：使用递归构建左子树和右子树。要记一些节点位置**/
        // 创建当前的根结点，并且为结点赋值。赋的值为根节点的值！
        BinaryTreeNode node = new BinaryTreeNode(); 
        node.value = value;
        // 递归构建当前根结点的左子树，左子树的元素个数：index-is+1个 
        // 左子树对应的前序遍历的位置在[ps+1, ps+index-is] 
        // 左子树对应的中序遍历的位置在[is, index-1] 
        node.left = construct(preorder, ps + 1, ps + index - is, 
                              inorder, is, index - 1); 
        // 递归构建当前根结点的右子树，右子树的元素个数：ie-index个 
        // 右子树对应的前序遍历的位置在[ps+index-is+1, pe] 
        // 右子树对应的中序遍历的位置在[index+1, ie] 
        node.right = construct(preorder, ps + index - is + 1, pe, 
                               inorder, index + 1, ie);
        // 返回创建的根结点 
        return node;
    }
}

对树本身就不熟悉，所以用言语再整理一遍。

已知前序、中序，要重建二叉树并输出头节点。所以题目会给一个前序和一个中序的数组。

一定要给中序数组，只给前序和后序的话重建不了。