欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉搜索树与双向链表(剑指OFFER 面试题36)

程序员文章站 2024-03-18 10:48:10
...

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思路

在二叉树中,每个节点都有两个指向子节点的指针。在双向链表中,每个节点也有两个指针,分别一个指向前一个指向后。由于这两种结构相似,同时二叉搜索树也是一中排序的数据结构,因此,理论上可以实现搜索二叉树和双向链表的转换。
在搜索二叉树中,左子节点的值总是小于父节点的值,右子节点的值总是大于父节点的值。因此,我们在将二叉搜索树转换成排序双向链表时,原先指向左子节点的指针调整为链表中指向前一个节点的指针。接下来就是转换问题了。
由于要求转换之后的链表是排好序的,所以我们可以中序遍历树中的每个节点。当遍历到根节点的时候,我们把树看成三个部分:
第一个部分,根节点部分;
第二个部分,根节点的左子树部分;
第三个部分,根节点的右子树部分。
根据排序链表的定义,根节点将它左子树的最大一个节点连接起来,同时将它和右子树的最小的节点连接起来,如下图:
二叉搜索树与双向链表(剑指OFFER 面试题36)
注:根节点、左子树、右子树。把左右子树转换成排序双向链表之后再和根节点连接起来,整颗二叉搜索树也就转换成了排序双向链表。

按照中序遍历的顺序,当我们遍历转换到根节点时,它的左子树已经转换成一个排序的链表了,并且处在链表中的最后一个节点是当前值最大的节点。接下来,遍历转换右子树,并把根节点和右子树中最小的节点连接起来,至于怎么去转换它的左子树和右子树,可以通过递归来实现。

测试案例

1、功能测试(输入的二叉树是完全二叉树;所有节点都没有左右子树的二叉树;只有一个节点的二叉树)
2、特殊输入测试(指向二叉树根节点的指针为null)

综上所述,以下为参考代码,测试就不一一测试了,只用一组测试来测试功能是否可行,代码已AC:

using System;

namespace 二叉搜索树与双向链表
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x)
        {
            val = x;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TreeNode tree = CreateTree();
            Solution s = new Solution();
            TreeNode convertList=s.Convert(tree);
        }

        /// <summary>
        /// 创建二叉搜索树
        /// </summary>
        /// <returns>二叉搜索树头节点</returns>
        private static TreeNode CreateTree()
        {
            TreeNode pNode = null;
                pNode = new TreeNode(10);
                pNode.left = new TreeNode(6);
                pNode.right = new TreeNode(14);
                pNode.left.left = new TreeNode(4);
                pNode.left.right = new TreeNode(8);
                pNode.right.left = new TreeNode(12);
                pNode.right.right = new TreeNode(16);

            return pNode;
        }
    }

    class Solution
    {
        /// <summary>
        /// 把二叉树转化成链表
        /// </summary>
        /// <param name="pRootOfTree">树的根节点</param>
        /// <returns>链表的头节点</returns>
        public TreeNode Convert(TreeNode pRootOfTree)
        {
            if(pRootOfTree==null)
                return null;
            //定义一个指向链表尾节点的指针
            TreeNode lastNode = null;
            //把二叉树的所有节点以中序的顺序添加进链表
            Convert(pRootOfTree,ref lastNode);

            //定义一个头指针,从尾节点往前遍历,指向头节点,然后返回头节点
            TreeNode headNode = lastNode;
            while (headNode != null && headNode.left != null)
                headNode = headNode.left;

            return headNode;
        }

        /// <summary>
        /// 把二叉树的节点以中序遍历的方式添加到链表中
        /// </summary>
        /// <param name="pNode">二叉树的头节点</param>
        /// <param name="lastNode">链表的尾节点</param>
        private void Convert(TreeNode pNode, ref TreeNode lastNode)
        {
            if (pNode == null)
                return;

            //定义指向当前节点的指针
            TreeNode curNode = pNode;
            //找到最左边的节点(当前树中最小值的节点)
            if (curNode.left != null)
                Convert(curNode.left, ref lastNode);
            //定义当前节点的前指针和链表最后节点的后指针
            curNode.left = lastNode;

            //如果链表为空,则让当前节点为链表的头节点
            if (lastNode != null)
                lastNode.right = curNode;
            //链表的尾指针指向链表的新尾节点
            lastNode = curNode;
            //如果当前节点有右节点,则把右节点添加进链表中
            if (curNode.right != null)
                Convert(curNode.right,ref lastNode);
        }
    }
}

在上面代码中 ,我们用lastNode指向已经转换好的链表的最后一个节点。当我们遍历到值为10的节点时,它的左子树都转换好了,因此lastNode的值指向8。接着把根节点连接到链表中之后,值为10的根节点成为了链表中的最后一个节点,于是lastNode指向了这个值为10的节点。接下来,把lastNode作为参数传入函数递归遍历右子树中最左边的子节点,并把该节点和值为10的节点连接起来。