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

import java.util.*;

/**
 * 树节点的定义
 */
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 将二叉搜索树转换为排序的双向循环链表
     * @param pRootOfTree 二叉搜索树的根节点
     * @return 排序的双向循环链表的头节点
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        if (pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
        
        // 将二叉搜索树转换为循环双向链表
        TreeNode res = ConvertToCircularList(pRootOfTree);
        
        // 打破循环结构，返回链表头节点
        res.left.right = null;
        res.left = null;
        
        return res;
    }

    /**
     * 将二叉搜索树转换为循环双向链表
     * @param pRootOfTree 二叉搜索树的根节点
     * @return 循环双向链表的头节点
     */
    private TreeNode ConvertToCircularList(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        
        // 将左右子树转换为循环双向链表
        TreeNode leftHead = ConvertToCircularList(pRootOfTree.left);
        TreeNode rightHead = ConvertToCircularList(pRootOfTree.right);
        
        // 使当前节点成为循环双向链表
        pRootOfTree.left = pRootOfTree;
        pRootOfTree.right = pRootOfTree;
        
        TreeNode res = pRootOfTree;
        
        // 合并左子链表和当前节点链表
        if (leftHead != null) {
            res = combineTwoTreeNodes(leftHead, res);
        }
        
        // 合并右子链表和当前节点链表
        if (rightHead != null) {
            res = combineTwoTreeNodes(res, rightHead);
        }
        
        return res;
    }

    /**
     * 合并两个循环双向链表
     * @param left 左子链表的头节点
     * @param right 右子链表的头节点
     * @return 合并后的循环双向链表的头节点
     */
    public TreeNode combineTwoTreeNodes(TreeNode left, TreeNode right) {
        TreeNode res = left;
        TreeNode tmp = left.left;
        TreeNode tmp1 = right.left;
        
        // 连接左子链表的尾节点和右子链表的头节点
        left.left = right.left;
        right.left = tmp;
        
        // 连接右子链表的尾节点和左子链表的头节点
        tmp.right = right;
        tmp1.right = left;
        
        return res;
    }
}