剑指Offer_6_重建二叉树

2017-03-16

题目描述

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

解题思路

先序遍历的结果第一个节点一定是根节点
根据先序遍历的第一个节点，即根节点，确定中序遍历中根节点的位置记为index
中序遍历中根节点的左边都是左子树上的节点，右边都是右子数上的节点
先序遍历中，前面index长度的节点为左子树，之后的都为右子树的节点
递归构建左右子树

详细解释

在二叉树的先序遍历中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列中间，
左子树的节点值位于根节点的值的左边，而右子树的节点的值位于根节点的右边。因此我们需要扫描
中序遍历序列，才能找到根节点的值。

由于在中序遍历序列中，有n个数字是左子树节点的值，因此左子树总共有n个左子节点。同样，在先序
遍历中，根节点后边的n个数字就是n个左子树节点的值右子树节点的值。这样我们就在先序和中序遍历
的两个序列中，分别找到了左右子树对应的子序列。

既然我们已经分别找到了左右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别取构建
左右子树。

代码实现

public class MakeTree
{
    /**
     * 构建一颗随机值的二叉树
     *
     * @Author NikoBelic
     * @Date 16/03/2017 20:36
     */
    public static void buildRandomTree(TreeNode root, int deep)
    {
        int type = new Random().nextInt(100) % 3;
        //int type = 0; // 构建满二叉树
        if (deep > 0)
        {
            if (type == 0) // 左+右
            {
                root.left = new TreeNode(new Random().nextInt(10));
                root.right = new TreeNode(new Random().nextInt(10));
                System.out.print("left-" + root.left.val);
                System.out.println("right-" + root.right.val);
                buildRandomTree(root.left, deep - 1);
                buildRandomTree(root.right, deep - 1);
            } else if (type == 1)
            {
                root.left = new TreeNode(new Random().nextInt(10));
                System.out.println("left-" + root.left.val);
                buildRandomTree(root.left, deep - 1);
            } else
            {
                root.right = new TreeNode(new Random().nextInt(10));
                System.out.println("right-" + root.right.val);
                buildRandomTree(root.right, deep - 1);
            }
        } else
            return;
    }
    /**
     * 广度优先遍历二叉树
     *
     * @Author NikoBelic
     * @Date 16/03/2017 20:36
     */
    public static void bfs(TreeNode node)
    {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(node);
        while (!q.isEmpty())
        {
            node = q.pop();
            System.out.println(node.val);
            if (node.left != null)
                q.addLast(node.left);
            if (node.right != null)
                q.addLast(node.right);
        }
    }
    /**
     * 按照中序、先序遍历结果，重新构建二叉树
     *
     * @Author SeawayLee
     * @Date 2017/03/21 19:17
     */
    public static TreeNode constructCore(int[] preVisit, int[] midVisit)
    {
        if (preVisit == null || midVisit == null)
            return null;
        // 创建root节点
        int rootValue = preVisit[0];
        TreeNode root = new TreeNode(rootValue);
        // 只有一个节点
        if (preVisit.length == 1)
        {
            if (midVisit.length == 1 && preVisit[0] == midVisit[0])
                return root;
            else
                System.out.println("Invalid Input...");
        }
        // 在中序遍历中找到根节点
        int rootIndex = 0;
        while (rootIndex <= midVisit.length - 1 && midVisit[rootIndex] != rootValue)
        {
            rootIndex++;
        }
        // 构建左子树
        int[] preLeft = Arrays.copyOfRange(preVisit, 1, rootIndex + 1);
        int[] midLeft = Arrays.copyOfRange(midVisit, 0, rootIndex);
        if (preLeft.length > 0)
        {
            root.left = constructCore(preLeft, midLeft);
        }
        // 构建右子树
        int[] preRight = Arrays.copyOfRange(preVisit, rootIndex + 1, preVisit.length);
        int[] midRight = Arrays.copyOfRange(midVisit, rootIndex + 1, midVisit.length);
        if (preRight.length > 0)
        {
            root.right = constructCore(preRight, midRight);
        }
        return root;
    }
    public static void main(String[] args) throws InterruptedException
    {
        //TreeNode root = new TreeNode(0);
        //buildRandomTree(root, 3);
        TreeNode root = constructCore(new int[]{1, 2, 4, 7, 3, 5, 6, 8}, new int[]{4, 7, 2, 1, 5, 3, 8, 6});
        bfs(root);
    }
}