剑指Offer（二十六）：二叉搜索树与双向链表

2017年12月14日11:28:48 15 6,902 °C
摘要

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

剑指Offer（二十六）：二叉搜索树与双向链表

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

举例说明：

剑指Offer（二十六）：二叉搜索树与双向链表

二叉搜索树如上图所示，我们将其转换为配需双向链表。

根据二叉搜索树的特点：左结点的值<根结点的值<右结点的值，我们不难发现，使用二叉树的中序遍历出来的数据的数序，就是排序的顺序。因此，首先，确定了二叉搜索树的遍历方法。

接下来，我们看下图，我们可以把树分成三个部分：值为10的结点、根结点为6的左子树、根结点为14的右子树。根据排序双向链表的定义，值为10的结点将和它的左子树的最大一个结点链接起来，同时它还将和右子树最小的结点链接起来。

剑指Offer（二十六）：二叉搜索树与双向链表

 

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

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        //用于记录双向链表尾结点
        TreeNode* pLastNodeInList = NULL;
        
        //开始转换结点
        ConvertNode(pRootOfTree, &pLastNodeInList);
        
        //pLastNodeInList指向双向链表的尾结点，我们需要重新返回头结点
        TreeNode* pHeadOfList = pLastNodeInList;
        while(pHeadOfList != NULL && pHeadOfList->left != NULL){
            pHeadOfList = pHeadOfList->left;
        }
        return pHeadOfList;
    }
    
    void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList){
        //叶结点直接返回
        if(pNode == NULL){
            return;
        }
        TreeNode* pCurrent = pNode;
        //递归左子树
        if(pCurrent->left != NULL)
            ConvertNode(pCurrent->left, pLastNodeInList);
        
        //左指针
        pCurrent->left = *pLastNodeInList;
        //右指针
        if(*pLastNodeInList != NULL){
            (*pLastNodeInList)->right = pCurrent;
        }
        //更新双向链表尾结点
        *pLastNodeInList = pCurrent;
        //递归右子树
        if(pCurrent->right != NULL){
            ConvertNode(pCurrent->right, pLastNodeInList);
        }
    }
};

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：15   其中：访客  9   博主  6

    • avatar 寄生 来自天朝的朋友 QQ浏览器 Windows 10 陕西省榆林市 电信 2
      回复 2018年6月11日 上午1:07  沙发

      博主，这篇文章移至没搞懂一个东西就是实参pLastNodeInList为什么传地址呢？同学上次给我说是为了递归进行时可以传pLastNodeInList的值，但是感觉递归函数一级指针也可以用，难道是为了最后更新pLastNodeInList，以便在主函数可以直接用这个值找到开头吗？

        • avatar Jack Cui Admin 来自天朝的朋友 火狐浏览器 Windows 7 北京市 百度网讯科技联通节点
          回复 2018年6月11日 上午9:53  1层

          @寄生 TreeNode* pLastNodeInList本身就是一个指针，需要使用二级指针存其地址进行操作。你同学说的没错。

            • avatar 寄生 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省西安市 电信 2
              回复 2018年6月11日 下午2:28  2层

              @Jack Cui 我又想了下，理解了点，谢谢啦

              • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                回复 2018年7月19日 上午10:33  2层

                @Jack Cui 楼主在百度实习吗？

                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                    回复 2018年7月19日 上午10:38  3层

                    @发文 嗯，是的。

                      • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                        2018年7月19日 上午10:56  4层

                        @Jack Cui 楼主做算法吗？能否帮忙内推。。。

                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                        回复 2018年7月19日 上午11:06  3层

                        @发文 嗯嗯，可以。c411184003@gmail.com发简历就行。

                  • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                    回复 2018年7月19日 上午10:43  板凳

                    提一个意见 为啥代码双击就变白了

                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                        回复 2018年7月19日 上午10:48  1层

                        @发文 这个是代码高亮插件的问题，对于这个我也很无奈。

                      • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                        回复 2018年7月19日 上午10:55  地板

                        设P为指针变量。
                        &p:指针变量自身地址
                        p: 指针变量所存储的值，即所指向的变量的地址
                        *p：指针所指向变量的值
                        所以要在传参时改变指针的值需要用一个指针来指向这个指针的位置，即二级指针；在传参时需要把这个指针的地址传过去。

                        • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                          回复 2018年7月19日 上午11:50  4楼

                          line39:将当前节点的左指针指向已经转换好的链表的最后一个位置
                          line45: *pLastNodeInList = pCurrent; 修改指针所指的变量的值，即修改所指向的指针的指向。

                          • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                            回复 2018年7月19日 下午12:03  5楼

                            有个疑问哈，22行，直接while( pHeadOfList->left != NULL)不可以吗？

                              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                                回复 2018年7月19日 下午12:51  1层

                                @发文 当然不行啊，当前的节点得判断。

                                  • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
                                    回复 2018年7月19日 下午1:07  2层

                                    @Jack Cui 有子节点不就说明当前节点非空吗？

                                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                                        回复 2018年7月19日 下午1:42  3层

                                        @发文 得先判断当前节点有没有啊….当前节点都没有，就left，直接段错误啊。