题目描述

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

在完成代码之前，我自己分析了一下如何根据前序遍历和中序遍历的结果构建一棵二叉树。首先，根据二叉树遍历的性质，由前序遍历的结果序列可知该二叉树的根节点是1，在根据中序遍历的结果可是根节点1的左子树包含的结点是4、7、2，右子树包含的节点是5、3、8、6。现在考虑左子树中节点4、7、2，由于这三个节点在前序遍历的结果是2、4、7，那么2必然是这三个节点组成的子树的根节点，再回到中序遍历的结果4、7、2，那么可以判断出4是2的左孩子，7是4的右孩子；同理可以对右子树进行判断。这样，画出的二叉树是这样的：

自然，我们可以分析判断过程写出构建二叉树的完整代码：

package com.rhwayfun.offer;

public class ConstructBinaryTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

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

    private TreeNode constructCore(int[] pre,int startPreOrder, int endPreOrder, int[] in,int startInOrder, int endInOrder) {
        //根据前序遍历找到根节点的值
        int rootValue = pre[startPreOrder];
        TreeNode rootNode = new TreeNode(rootValue);
        rootNode.left = null;
        rootNode.right = null;

        //只有一个结点，那么该节点就是根节点，直接返回
        if(startPreOrder == endPreOrder){
            if(startInOrder == endInOrder && pre[startPreOrder] == in[startInOrder]){
                return rootNode;
            }
        }

        //根据中序遍历的结果找到根节点
        int rootOfInOrder = startInOrder;
        while(rootOfInOrder <= endInOrder && in[rootOfInOrder] != rootValue){
            rootOfInOrder++;
        }

        //异常处理
        if(rootOfInOrder == endInOrder && in[rootOfInOrder] != rootValue){
            return null;
        }

        //计算左子树的长度
        int leftSubTreeLen = rootOfInOrder - startInOrder;
        //根据左子树的长度计算前序遍历结果中左子树的最后一个结点的下标
        int leftIndexOfPreOrderEnd = startPreOrder + leftSubTreeLen;
        //重建左子树
        if(leftSubTreeLen > 0){
            rootNode.left = constructCore(pre, startPreOrder + 1, leftIndexOfPreOrderEnd, in, startInOrder, rootOfInOrder - 1);
        }
        //重建右子树
        if(leftSubTreeLen < endPreOrder - startPreOrder){
            rootNode.right = constructCore(pre, leftIndexOfPreOrderEnd + 1, endPreOrder, in, rootOfInOrder + 1, endInOrder);
        }
        return rootNode;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = new ConstructBinaryTree().reConstructBinaryTree(pre, in);
        System.out.println(root);
    }
}