C/C++ BM30 二叉搜索树与双向链表

前言

这道题要明白二叉搜索树的概念，同时还要对链表的知识比较熟悉。

---

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 $0\le n\le 1000$，二叉树中每个节点的值 $0\le val\le 1000$
要求：空间复杂度$O(1)$（即在原树上操作），时间复杂度 $O(n)$

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。

示例1
输入：{10,6,14,4,8,12,16}
返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

解决方案一

1.1 思路阐述

二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

直到了二叉搜索树的概念，那我们可以通过中序遍历的方式进行取值，将取出来的值存放到一个数组中去，再将数组的节点进行两两绑定。

为什么用中序遍历，因为二叉搜索树的话，使用中序遍历可以保证取出来的值一定是从左往右，由小到大。

1.2 源码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<TreeNode*> TreeList;//定义一个数组，根据中序遍历来存储结点。

    void inorder(TreeNode* root){
        if (!root) return;
        inorder(root->left);
        TreeList.push_back(root);
        inorder(root->right);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (!pRootOfTree) return pRootOfTree;
        inorder(pRootOfTree);
        for (int i=0;i<TreeList.size()-1;i++){ //根据数组中的顺序将结点连接，注意i的范围。
            TreeList[i]->right = TreeList[i+1];
            TreeList[i+1]->left = TreeList[i];
        }
        return TreeList[0];//数组的头部存储的是双向链表的第一个结点。
    }

};
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

解决方案二

2.1 思路阐述

这里摘的是精华题解的一种，这个是满足了题目要求的。

1. 首先我们要想办法确定链表的头节点, 只要不断向左递归到最后一个节点即可确定
2. 其次我们要确定将前后两个节点连接起来的方案, 我们定义两个指针cur和pre, cur的当前节点的指针, pre是cur的前驱节点的指针, 因此只要pre不为空, 连接方案就是pre->right = cur, cur->left = pre
3. 二叉树中序遍历的顺序是左儿子->根节点->右儿子, 故我们只要按中序遍历的顺序移动pre和cur指针, 就可以将整个二叉树连接为一条双向链表

2.2 源码

class Solution {
  public:
    TreeNode* head, *pre;

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == nullptr) return pRootOfTree;   // 若为空树返回空指针
        pre = nullptr;    // 初始化pre指针, 用于确定head节点
        inorder(pRootOfTree);
        return head;
    }

    void inorder(TreeNode* cur) {
        if (cur == nullptr) return;   // 当前节点为空, 返回

        inorder(cur->left);    // 向左递归

        if (pre == nullptr) head = cur;   // 此时cur是最左侧的节点, 即根节点
        else {   // pre不为空, 按规定方案连接
            pre->right = cur;
            cur->left = pre;
        }
        pre = cur;  // 更新pre指针

        inorder(cur->right);    // 向右递归
    }
};
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

总结

回顾了一下中序遍历，对二叉搜索树的理解更进一步。