[数据结构与算法]二叉搜索树与双向链表

题目

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

思路

• 递归中序遍历(有序)构造双向链表
• 首尾相接循环双向链表

代码

/*
// 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 {
    //head表示首
    //tail表示尾
    Node head,tail;
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }
        dfs(root);
        //首尾拼接
        head.left=tail;
        tail.right=head;

        return head;


    }

    public void dfs(Node cur){
        if(cur==null){
            return;
        }

        dfs(cur.left);

        //构造双向链表
        if(tail!=null){
            tail.right=cur;
        }else{
            head=cur;
        }

        cur.left=tail;
        tail=cur;
        dfs(cur.right);
    }
}

复杂度

时间复杂度： O(n)
空间复杂度： O(1)