题解 | #二叉搜索树与双向链表#

class Solution {
  public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        // 如果树为空，则直接返回nullptr
        if (pRootOfTree == nullptr) {
            return nullptr;
        }

        TreeNode* prev = nullptr; // 用于跟踪当前节点的前一个节点
        TreeNode* head = nullptr; // 用于记录链表的头节点

        // 执行中序遍历，并在遍历过程中调整节点指针以形成双向链表
        inorder(pRootOfTree, prev, head);

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

  private:
    void inorder(TreeNode* node, TreeNode*& prev, TreeNode*& head) {
        // 如果当前节点为空，则直接返回
        if (node == nullptr) {
            return;
        }

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

        // 处理当前节点
        if (prev != nullptr) {
            // 如果前一个节点存在，则设置前一个节点的右指针指向当前节点，并设置当前节点的左指针指向前一个节点
            prev->right = node;
            node->left = prev;
        } else {
            // 如果前一个节点不存在，则当前节点是链表的头节点
            head = node;
        }

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

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