每日一题-二叉搜索树与双向链表

将二叉搜索树转化为排序双向链表

问题描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表，要求空间复杂度为 O(1)，时间复杂度为 O(n)，并且不能创建新的结点，只能调整树中结点的指针指向。

数据范围

• 二叉树的节点数：$0\le n\le 1000$
• 每个节点的值：$0\le val\le 1000$

解决方案

1. 要求：不能创建新的结点，只能调整树中结点指针的指向。转换完成后，树中节点的左指针需要指向前驱，右指针需要指向后继。
2. 返回：返回链表中的第一个节点的指针。
3. 结构：链表的节点就是原树的节点，每个节点的左指针指向前驱，右指针指向后继。

示例

• 输入：{10, 6, 14, 4, 8, 12, 16}

• 输出：从左到右是：4, 6, 8, 10, 12, 14, 16；从右到左是：16, 14, 12, 10, 8, 6, 4。

• 输入：{5, 4, #, 3, #, 2, #, 1}

• 输出：从左到右是：1, 2, 3, 4, 5；从右到左是：5, 4, 3, 2, 1。

代码实现

/**
 * 定义二叉树节点结构
 * 树节点包含一个整数值 `val`，指向左子节点 `left` 和右子节点 `right` 的指针
 */

/**
 * 中序遍历函数，将二叉搜索树转化为双向链表
 * @param node 当前节点
 * @param prev 指向前一个节点的指针，用于连接当前节点
 * @param head 指向链表头节点的指针
 */
void inOrderTraversal(struct TreeNode* node, struct TreeNode** prev,
                      struct TreeNode** head) {
    // 递归终止条件：节点为空时返回
    if (node == NULL) {
        return;
    }

    // 先遍历左子树
    inOrderTraversal(node->left, prev, head);

    // 处理当前节点
    if (*prev) {  // 如果前一个节点存在
        (*prev)->right = node;  // 前驱节点的右指针指向当前节点
        node->left = *prev;     // 当前节点的左指针指向前驱节点
    } else {  // 如果是链表的第一个节点
        *head = node;  // 第一个节点就是链表的头节点
    }

    // 更新prev为当前节点
    *prev = node;  // 前一个节点更新为当前节点

    // 再遍历右子树
    inOrderTraversal(node->right, prev, head);
}

/**
 * 将二叉搜索树转换为双向链表
 * @param pRootOfTree 二叉树的根节点
 * @return 双向链表的头节点
 */
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    // 如果根节点为空，直接返回NULL
    if (!pRootOfTree) return NULL;

    // prev指针用于记录中序遍历中的前一个节点
    struct TreeNode* prev = NULL;
    // head指针用于记录链表的头节点
    struct TreeNode* head = NULL;

    // 调用中序遍历函数，完成树转链表
    inOrderTraversal(pRootOfTree, &prev, &head);

    // 返回链表的头节点
    return head;
}

关键概念

1. 中序遍历：二叉搜索树的中序遍历是递增的。因此，通过中序遍历的顺序将二叉树节点连接成双向链表，即可确保双向链表是有序的。

2. 指针传递：在递归过程中，prev 和 head 使用指针的指针传递（即 struct TreeNode**）。这可以确保在递归过程中修改这些指针的值时，外部调用者也能看到这些修改。

为什么 struct TreeNode** prev 和 struct TreeNode** head？

我一直在思考为什么TreeNode** prev, struct TreeNode** head，而不是TreeNode* prev, struct TreeNode* head，后来才意识到在函数 inOrderTraversal 中，prev 和 head 是作为值传递给递归函数的。由于 C 语言中函数传递的是值，而不是引用，所以在递归过程中修改 prev 和 head 的值不会影响到外部的 prev 和 head。
为了解决这个问题，我们需要使用 struct TreeNode** 来传递指针的指针。可以把 struct TreeNode当作一个数据类型int，然后再 struct TreeNode**类比int指针。完美。
在递归过程中，prev 和 head 是作为指针传递的。如果直接使用 struct TreeNode*，那么修改的是它们的副本，无法影响到外部的实际值。通过传递 struct TreeNode**，递归函数可以修改指针本身，从而影响到实际的 prev 和 head 指针。