二叉搜索树转换为排序双向链表的面试题解析

题目背景

给定一棵二叉搜索树，任务是将其转换为一个排序的双向链表，转换过程中不能创建任何新的节点，只能通过调整树中节点的指针来完成这一操作。例如，输入如图所示的二叉搜索树，输出结果应为转换后的排序双向链表。

解题思路

解题的关键在于利用二叉搜索树的性质——左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。基于这一特性，我们可以采用中序遍历的方式，首先将左子树转换为双向链表，然后将根节点插入到左子树形成的链表中，最后将右子树也转换为双向链表并连接到根节点上。整个过程可以通过递归来实现，每次递归调用处理一个节点及其左右子树。

实现代码

以下是C++语言实现的代码示例，展示了如何将二叉搜索树转换为双向链表：

#pragma once
#ifndef BINARY_TREE_TO_DOUBLE_LINKED_LIST_H
#define BINARY_TREE_TO_DOUBLE_LINKED_LIST_H

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

class TreeConverter {
public:
    TreeConverter() {}
    ~TreeConverter() {}
    TreeNode* convert(TreeNode* root);
private:
    void convertNode(TreeNode* node, TreeNode*& lastNode);
};

#endif // BINARY_TREE_TO_DOUBLE_LINKED_LIST_H

#include "TreeConverter.h"

TreeNode* TreeConverter::convert(TreeNode* root) {
    TreeNode* lastNode = nullptr;
    convertNode(root, lastNode);
    TreeNode* head = lastNode;
    while (head != nullptr && head->left != nullptr) {
        head = head->left;
    }
    return head;
}

void TreeConverter::convertNode(TreeNode* node, TreeNode*& lastNode) {
    if (node == nullptr) return;
    if (node->left != nullptr) convertNode(node->left, lastNode);
    node->left = lastNode;
    if (lastNode != nullptr) lastNode->right = node;
    lastNode = node;
    if (node->right != nullptr) convertNode(node->right, lastNode);
}