📃 题目描述

题目链接：剑指 Offer 36. 二叉搜索树与双向链表 (opens new window)

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

🔔 解题思路

和 剑指 Offer II 052. 展平二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 基本差不多

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        Stack<Node> stack = new Stack<>();
        Node cur = root;
        Node pre = null;
        Node head = null;

        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();

            if (pre == null) {
                head = cur;
            }
            else {
                pre.right = cur;
            }

            cur.left = pre;
            
            pre = cur;
            cur = cur.right;
        }

        // 首尾连起来
        head.left = pre;
        pre.right = head;

        return head;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：