专栏首页EdisonTalk剑指Offer面试题:5.重建二叉树

剑指Offer面试题:5.重建二叉树

一、题目:重建二叉树

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

二、解题思路

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

  前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列,就能确定根结点的值的位置。根据中序遍历特点,在根结点的值1前面的3个数字都是左子树结点的值,位于1后面的数字都是右子树结点的值。

  在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值的步骤如下图所示:

  分别找到了左、右子树的前序遍历序列和中序遍历序列,我们就可以用同样的方法分别去构建左右子树。换句话说,这是一个递归的过程。

思路总结:先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后,就可以递归地去分别构建它的左右子树。

三、解决问题

3.1 代码实现

    public static Node<int> Construct(int[] preOrder, int[] inOrder, int length)
    {
        // 空指针判断
        if (preOrder == null || inOrder == null || length <= 0)
        {
            return null;
        }

        return ConstructCore(preOrder, 0, preOrder.Length - 1, inOrder, 0, inOrder.Length - 1);
    }

    public static Node<int> ConstructCore(int[] preOrder, int startPreOrder, int endPreOrder, int[] inOrder, int startInOrder, int endInOrder)
    {
        // 前序遍历序列的第一个数字是根结点的值
        int rootValue = preOrder[startPreOrder];
        Node<int> root = new Node<int>();
        root.data = rootValue;
        root.lchild = root.rchild = null;

        if (startPreOrder == endPreOrder)
        {
            if (startInOrder == endInOrder && 
                preOrder[startPreOrder] == inOrder[startInOrder])
            {
                return root;
            }
            else
            {
                throw new Exception("Invalid input!");
            }
        }

        // 在中序遍历中找到根结点的值
        int rootInOrder = startInOrder;
        while (rootInOrder <= endInOrder && inOrder[rootInOrder] != rootValue)
        {
            rootInOrder++;
        }

        // 输入的两个序列不匹配的情况
        if (rootInOrder == endInOrder && inOrder[rootInOrder] != rootValue)
        {
            throw new Exception("Invalid input!");
        }

        int leftLength = rootInOrder - startInOrder;
        int leftPreOrderEnd = startPreOrder + leftLength;
        if (leftLength > 0)
        {
            // 构建左子树
            root.lchild = ConstructCore(preOrder, startPreOrder + 1, leftPreOrderEnd, inOrder, startInOrder, rootInOrder - 1);
        }
        if (leftLength < endPreOrder - startPreOrder)
        {
            // 构建右子树
            root.rchild = ConstructCore(preOrder, leftPreOrderEnd + 1, endPreOrder, inOrder, rootInOrder + 1, endInOrder);
        }

        return root;
    }

3.2 单元测试

  首先封装了一个测试主入口,方法定义如下:

    // 单元测试主入口
    public static void ConstructTestPortal(string testName, int[] preOrder, int[] inOrder, int length)
    {
        if (!string.IsNullOrEmpty(testName))
        {
            Console.WriteLine("{0} begins:", testName);
        }
        // 打印先序遍历
        Console.Write("The preorder sequence is : ");
        for (int i = 0; i < length; i++)
        {
            Console.Write(preOrder[i]);
        }
        Console.Write("\n");
        // 打印中序遍历
        Console.Write("The inorder sequence is : ");
        for (int i = 0; i < length; i++)
        {
            Console.Write(inOrder[i]);
        }
        Console.Write("\n");

        try
        {
            Node<int> root = Construct(preOrder, inOrder, length);
            BinaryTree<int> bTree = new BinaryTree<int>();
            bTree.Root = root;
            Console.Write("The binary tree is : ");
            // 重建的二叉树层次遍历
            bTree.LevelOrder(bTree.Root);
            if (!string.IsNullOrEmpty(testName))
            {
                Console.Write("\n{0} end\n\n", testName);
            }
        }
        catch (Exception)
        {
            Console.WriteLine("Invalid input!");
        }
    }

  该方法首先接收参数,依次打印先序遍历和中序遍历,最后通过调用Construct方法获得重建的二叉树的根节点,并实例化一个二叉树的数据结构(本处的二叉树结构的实现请阅读《数据结构基础温故-4.树与二叉树(上)》),最后输出重建后的二叉树的层次遍历验证是否重建成功。

  (1)普通二叉树

    // 普通二叉树
    //              1
    //           /     \
    //          2       3  
    //         /       / \
    //        4       5   6
    //         \         /
    //          7       8
    public static void ConstructTest1()
    {
        int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8 };
        int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };

        ConstructTestPortal("ConstructTest1", preorder, inorder, 8);
    }

  (2)所有结点都没有右子结点

    // 所有结点都没有右子结点
    //            1
    //           / 
    //          2   
    //         / 
    //        3 
    //       /
    //      4
    //     /
    //    5
    public static void ConstructTest2()
    {
        int[] preorder = { 1, 2, 3, 4, 5 };
        int[] inorder = { 5, 4, 3, 2, 1 };

        ConstructTestPortal("ConstructTest2", preorder, inorder, 5);
    }

  (3)所有结点都没有左子结点

    // 所有结点都没有左子结点
    //            1
    //             \ 
    //              2   
    //               \ 
    //                3 
    //                 \
    //                  4
    //                   \
    //                    5
    public static void ConstructTest3()
    {
        int[] preorder = {1, 2, 3, 4, 5};
        int[] inorder = {1, 2, 3, 4, 5};

        ConstructTestPortal("ConstructTest3", preorder, inorder, 5);
    }

  (4)树中只有一个结点

    // 树中只有一个结点
    public static void ConstructTest4()
    {
        int[] preorder = { 1 };
        int[] inorder = { 1 };

        ConstructTestPortal("ConstructTest4", preorder, inorder, 1);
    }

  (5)完全二叉树

    // 完全二叉树
    //              1
    //           /     \
    //          2       3  
    //         / \     / \
    //        4   5   6   7
    public static void ConstructTest5()
    {
        int[] preorder = {1, 2, 4, 5, 3, 6, 7};
        int[] inorder = {4, 2, 5, 1, 6, 3, 7};

        ConstructTestPortal("ConstructTest5", preorder, inorder, 7);
    }

  (6)输入空指针

    // 输入空指针
    public static void ConstructTest6()
    {
        ConstructTestPortal("ConstructTest6", null, null, 0);
    }

  (7)输入的两个序列不匹配

    // 输入的两个序列不匹配
    public static void ConstructTest7()
    {
        int[] preorder = {1, 2, 4, 5, 3, 6, 7};
        int[] inorder = {4, 2, 8, 1, 6, 3, 7};

        ConstructTestPortal("ConstructTest7", preorder, inorder, 7);
    }

  单元测试的结果如下图所示:

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你必须知道的指针基础-7.void指针与函数指针

      void *表示一个“不知道类型”的指针,也就不知道从这个指针地址开始多少字节为一个数据。和用int表示指针异曲同工,只是更明确是“指针”。

    Edison Zhou
  • 剑指Offer面试题:7.旋转数组的最小数字

      这道题最直观的解法并不难,从头到尾遍历数组一次,我们就能找出最小的元素。这种思路的时间复杂度显然是O(n)。但是这个思路没有利用输入的旋转数组的特性,肯定达...

    Edison Zhou
  • 数据结构基础温故-6.查找(上):基本查找与树表查找

    只要你打开电脑,就会涉及到查找技术。如炒股软件中查股票信息、硬盘文件中找照片、在光盘中搜DVD,甚至玩游戏时在内存中查找攻击力、魅力值等数据修改用来作弊等,都要...

    Edison Zhou
  • Android程序员经常遇到的算法问题,七大常用的算法

    插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在...

    Android技术干货分享
  • 1077: 输入入门(2)

    描述:计算A+B 输入:输入第1行为一个整数n(1≤n≤10),代表测试的组数。下面有n组测试数据,每组1行,为2个整数,为A, B。 输出:输出A+B的值...

    bboysoul
  • 对数据操作封装的一点心得

    在对数据进行操作时,可能需要读写name,于是我们写了一个接口,这个接口会实时更新缓存

    王亚昌
  • 【HDU 5839】Special Tetrahedron(计算几何)

    共面判断就是用叉乘计算出ijk三点所在面的法向量,然后判断il向量是否和法向量垂直,是则共面。

    饶文津
  • 根据后序和中序遍历输出先序遍历

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 与算法有关的习题二道

    在猿问上回答了几道题,其中二题还不错,记录一下 题一 要求输入一串不是很长的字符串,在最大的字符后加(max),字符串没有空格,只在第一个出现最大的字符后加(m...

    东风冷雪
  • LeetCode 261. 以图判树(全部连通+边数=V-1)

    给定从 0 到 n-1 标号的 n 个结点,和一个无向边列表(每条边以结点对来表示), 请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券