一、题目

1、题目描述

  二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。返回转换后的单向链表的头节点。
  样例输入： [4,2,5,1,3,null,6,0]
  样例输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

2、基础框架

• C语言 版本给出的基础框架代码如下：

1
2
3
struct TreeNode* convertBiNode(struct TreeNode* root){
}

3、原题链接

LeetCode 面试题 17.12. BiNode

二、解题报告

1、思路分析

  $(1)$ 首先，对于二叉搜索树的题目，我们想到的就是深度优先搜索。
  $(2)$ 对于这个题目，要求二叉搜索树的一个 “斜树”，也就是一个非常不平衡的二叉搜索树，对于二叉搜索树而言，左子树的所有元素都是小于根的，根的元素是小于所有的右子树的，所以在构建这棵 “斜树” 的时候，对于 “斜树” 中任意一个结点，它的链表父结点（right指向它的那个结点）一定在左子树上；它的right指向的结点一定在它的右子树上。
  $(3)$ 所以我们可以用一个深度优先搜索来求这个二叉搜索树。
  $(4)$ void dfs(struct TreeNode* root, struct TreeNode** head, struct TreeNode** tail)这个函数求的是什么呢？
  $(5)$ 它求的就是把一棵以root为根结点的二叉搜索树转换成一个 “斜树”，并且斜树的第一个根结点是 *head，最后一个叶子结点是*tail；
  $(6)$ 然后就是通过后序遍历，去实现这个函数。

2、时间复杂度

   $O(n^2)$

3、代码详解

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void dfs(struct TreeNode* root, struct TreeNode** head, struct TreeNode** tail) {
    struct TreeNode *lhead, *ltail, *rhead, *rtail;

    if(root == NULL) {
        *head = *tail = NULL;
        return ;
    }

    dfs(root->left, &lhead, &ltail);       // (1)

    if(ltail) {                            // (2)
        ltail->left = NULL;
        ltail->right = root;
    }

    dfs(root->right, &rhead, &rtail);      // (3)

    root->left = NULL;                     // (4)
    root->right = rhead;                   

    *head = lhead ? lhead : root;          // (5)
    *tail = rtail ? rtail : root;          // (6)
}


struct TreeNode* convertBiNode(struct TreeNode* root){
    struct TreeNode *head, *tail;
    dfs(root, &head, &tail);
    return head;
}

• $(1)$ 计算 root左子树的链表（斜树）头和尾；
• $(2)$ 如果左子树存在的话，则将左子树计算出来的尾结点指向当前结点；
• $(3)$ 计算 root右子树的链表（斜树）头和尾；
• $(4)$ 代表把当前结点root的right指针指向右子树的链表头结点；
• $(5)-(6)$ 返回当前这棵树的链表（斜树）头和尾；

三、本题小知识

  对于二叉树的题，75% 是可以通过深度优先搜索来实现的。剩下的是广度优先搜索。

四、加群须知

  相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
  那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：

  大致题集一览：

  为了让这件事情变得有趣，以及「 照顾初学者 」，目前题目只开放最简单的算法 「 枚举系列 」 （包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有 一半成员刷完 「 枚举系列 」 的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「 夜深人静写算法 」专家团 的一员。
  不要小看这个专家团，三年之后，你将会是别人 望尘莫及 的存在。如果要加入，可以联系我，考虑到大家都是学生， 没有「 主要经济来源 」，在你成为神的路上，「 不会索取任何 」。
  ????联系作者，或者扫作者主页二维码加群，加入刷题行列吧????

????让天下没有难学的算法????
C语言免费动漫教程，和我一起打卡！ ????《光天化日学C语言》????
让你养成九天持续刷题的习惯 ????《九日集训》????
入门级C语言真题汇总 ????《C语言入门100例》????
组团学习，抱团生长 ????《算法零基础100讲》????
几张动图学会一种数据结构 ????《画解数据结构》????
竞赛选手金典图文教程 ????《夜深人静写算法》????

最后

以上就是自信高跟鞋最近收集整理的关于LeetCode 面试题 17.12. BiNode一、题目二、解题报告三、本题小知识四、加群须知的全部内容，更多相关LeetCode内容请搜索靠谱客的其他文章。