C++如何将二叉搜索树转换成双向循环链表(双指针或数组)

将二叉搜索树转换成双向循环链表是一道比较经典的算法题，本文将对该算法进行完整讲解。

算法思路

我们可以将该问题划分成多个子问题：
- 将左子树转换为双向循环链表，并返回链表头和链表尾；
- 将右子树转换为双向循环链表，并返回链表头和链表尾；
- 将当前节点插入左子树的链表尾，将左子树链表尾连接至当前节点；
- 将当前节点插入右子树的链表头，将右子树链表头连接至当前节点；
- 最终返回整个链表的头节点。

算法的整体思路是通过递归遍历整棵树，将左右子树递归转换成双向循环链表，然后将当前节点与左右子树的链表连接起来，并返回整个链表的头节点。

代码如下：

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* treeToDoublyList(TreeNode* root) {
        if (!root) return nullptr;
        TreeNode *head, *tail;
        dfs(root, head, tail); // dfs是递归函数，将root转成链表，并返回头节点和尾节点
        head->left = tail; // 头节点的左指针指向尾节点
        tail->right = head; // 尾节点的右指针指向头节点
        return head;
    }

    void dfs(TreeNode* root, TreeNode* &head, TreeNode* &tail) {
        if (!root) { // 如果为空节点，则左右指向自己（这是为了后续方便处理）
            head = tail = nullptr;
            return;
        }
        TreeNode *lhead, *ltail, *rhead, *rtail;
        dfs(root->left, lhead, ltail); // 递归处理左子树
        dfs(root->right, rhead, rtail); // 递归处理右子树
        if (!lhead) { // 如果左子树为空，则用当前节点替代head
            head = root;
        } else {
            head = lhead; // 否则头节点为左子树的头节点
            ltail->right = root; // 左子树的尾节点连接到当前节点
            root->left = ltail; // 当前节点的左指针指向左子树的尾节点
        }
        if (!rhead) { // 如果右子树为空，则用当前节点替代tail
            tail = root;
        } else {
            tail = rtail; // 否则尾节点为右子树的尾节点
            rhead->left = root; // 右子树的头节点连接到当前节点
            root->right = rhead; // 当前节点的右指针指向右子树的头节点
        }
    }
};

示例说明

下面提供两个示例来说明该算法。

示例 1

给定一个二叉搜索树如下：

将该二叉搜索树转换成双向循环链表，并返回头节点。

实现过程：
1. 左子树为空，右子树非空。
2. 将右子树[5]转成双向循环链表，头节点为[5]，尾节点为[5]。
3. 将当前节点[4]插入右子树链表头，右子树链表头为[4]。
4. 将右子树链表头连接到当前节点，当前节点的右指针指向[5]，[5]的左指针指向当前节点。
5. 整个链表的尾节点为[5]，将尾节点的右指针连接到头节点，头节点的左指针连接到尾节点。

最终结果为：

1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 1

示例 2

给定一个二叉搜索树如下：

    2
   / \
  1   3

将该二叉搜索树转换成双向循环链表，并返回头节点。

实现过程：
1. 左子树非空，右子树非空。
2. 将左子树[1]转成双向循环链表，头节点为[1]，尾节点为[1]。
3. 将当前节点[2]插入左子树链表尾，左子树链表尾为[1]，当前节点的左指针指向[1]，[1]的右指针指向当前节点。
4. 将右子树[3]转成双向循环链表，头节点为[3]，尾节点为[3]。
5. 将当前节点[2]插入右子树链表头，右子树链表头为[3]，当前节点的右指针指向[3]，[3]的左指针指向当前节点。
6. 整个链表的尾节点为[1]，将尾节点的右指针连接到头节点，头节点的左指针连接到尾节点。