剑指Offer面试题:25.二叉搜索树与双向链表

一、题目:二叉搜索树与双向链表

题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。比如输入下图中左边的二叉搜索树,则输出转换之后的排序双向链表。

  二叉搜索树的节点定义如下,这里使用C#语言描述:

    public class BinaryTreeNode
    {
        public int Data { get; set; }
        public BinaryTreeNode leftChild { get; set; }
        public BinaryTreeNode rightChild { get; set; }

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
        {
            this.Data = data;
            this.leftChild = left;
            this.rightChild = right;
        }
    }

二、解题思路

2.1 核心步骤

  首先,我们知道:在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。

  其次,由于要求转换之后的链表是排好序的,我们可以中序遍历树中的每一个结点,这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。

  最后,按照中序遍历的顺序,当我们遍历转换到根结点(值为10的结点)时,它的左子树已经转换成一个排序的链表了,并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来,此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树,并把根结点和右子树中最小的结点链接起来。

  很明显,转换它的左子树和右子树,由于遍历和转换过程是一样的,很自然地想到可以用递归

2.2 代码实现

    public BinaryTreeNode Convert(BinaryTreeNode root)
    {
        BinaryTreeNode lastNodeInList = null;
        ConvertNode(root, ref lastNodeInList);

        // lastNodeInList指向双向链表的尾结点,
        // 我们需要返回头结点
        BinaryTreeNode headInList = lastNodeInList;
        while (headInList != null && headInList.leftChild != null)
        {
            headInList = headInList.leftChild;
        }

        return headInList;
    }

    private void ConvertNode(BinaryTreeNode node, ref BinaryTreeNode lastNodeInList)
    {
        if (node == null)
        {
            return;
        }

        BinaryTreeNode currentNode = node;
        // 转换左子树
        if (currentNode.leftChild != null)
        {
            ConvertNode(currentNode.leftChild, ref lastNodeInList);
        }
        // 与根节点的衔接
        currentNode.leftChild = lastNodeInList;
        if (lastNodeInList != null)
        {
            lastNodeInList.rightChild = currentNode;
        }
        lastNodeInList = currentNode;
        // 转换右子树
        if (currentNode.rightChild != null)
        {
            ConvertNode(currentNode.rightChild, ref lastNodeInList);
        }
    }

三、单元测试

3.1 测试用例

  (1)辅助方法的封装

    private void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild)
    {
        if (root == null)
        {
            return;
        }

        root.leftChild = lChild;
        root.rightChild = rChild;
    }

    private BSTConverter converter;

    [TestInitialize]
    public void Initialize()
    {
        converter = new BSTConverter();
    }

    [TestCleanup]
    public void CleanUp()
    {
        converter = null;
    }

  (2)功能测试、特殊输入测试

    //            10
    //         /      \
    //        6        14
    //       /\        /\
    //      4  8     12  16
    [TestMethod]
    public void ConvertTest1()
    {
        BinaryTreeNode node10 = new BinaryTreeNode(10);
        BinaryTreeNode node6 = new BinaryTreeNode(6);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node8 = new BinaryTreeNode(8);
        BinaryTreeNode node14 = new BinaryTreeNode(14);
        BinaryTreeNode node12 = new BinaryTreeNode(12);
        BinaryTreeNode node16 = new BinaryTreeNode(16);

        SetSubTreeNode(node10, node6, node14);
        SetSubTreeNode(node6, node4, node8);
        SetSubTreeNode(node14, node12, node16);

        BinaryTreeNode result = converter.Convert(node10);
        Assert.AreEqual(result, node4);
    }

    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    [TestMethod]
    public void ConvertTest2()
    {
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        node5.leftChild = node4;
        node4.leftChild = node3;
        node3.leftChild = node2;
        node2.leftChild = node1;

        BinaryTreeNode result = converter.Convert(node5);
        Assert.AreEqual(result, node1);
    }

    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    [TestMethod]
    public void ConvertTest3()
    {
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        node1.rightChild = node2;
        node2.rightChild = node3;
        node3.rightChild = node4;
        node4.rightChild = node5;

        BinaryTreeNode result = converter.Convert(node1);
        Assert.AreEqual(result, node1);
    }

    // 树中只有1个结点
    [TestMethod]
    public void ConvertTest4()
    {
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        BinaryTreeNode result = converter.Convert(node1);
        Assert.AreEqual(result, node1);
    }

    // 空指针
    [TestMethod]
    public void ConvertTest5()
    {
        BinaryTreeNode result = converter.Convert(null);
        Assert.AreEqual(result, null);
    } 

3.2 测试结果

  (1)测试通过情况

  (2)代码覆盖率

作者:周旭龙

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

本题详细的分析过程均在代码注释中: import java.util.Iterator; import java.util.Stack; /** * 题目:...

3035
来自专栏恰童鞋骚年

剑指Offer面试题:17.树的子结构

  为了方便测试,这里封装了一个设置指定根节点的左孩子和右孩子节点的方法:SetSubTreeNode

1042
来自专栏小白鼠

Tree

1012
来自专栏深度学习与计算机视觉

算法-重建二叉树

题目: 输入某二叉树的前序遍历与中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字,前序遍历序列为{},中序遍历序列为{},则重...

19410
来自专栏高性能服务器开发

算法导论第十二章 二叉搜索树

二叉搜索树(又名二叉查找树、二叉排序树)是一种可提供良好搜寻效率的树形结构,支持动态集合操作,所谓动态集合操作,就是Search、Maximum、Minimum...

1392
来自专栏机器学习实践二三事

二叉树的建立和各种遍历(java版)

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序 ->建树 假设现在有个二叉树,如下: ? 此时遍历顺序是: ...

2896
来自专栏aCloudDeveloper

算法导论第十二章 二叉搜索树

一、二叉搜索树概览   二叉搜索树(又名二叉查找树、二叉排序树)是一种可提供良好搜寻效率的树形结构,支持动态集合操作,所谓动态集合操作,就是Search、Max...

21610
来自专栏LeetCode

LeetCode <dfs>105&106 Construct Binary Tree

Given preorder and inorder traversal of a tree, construct the binary tree.

1566
来自专栏恰童鞋骚年

剑指Offer面试题:18.二叉树的镜像

Step1.先序遍历原二叉树的每个节点,如果遍历到的结点有子结点,就交换它的两个子结点。

851
来自专栏书山有路勤为径

二叉树-路径之和

给定一个二叉树与整数sum,找出所有从根节点到叶结点的路径,这些路径上的节点值累加和为sum。

732

扫码关注云+社区

领取腾讯云代金券