题目

思路

1. 看题目看了半天…意思应该是有一个完整的二叉搜索树，按从小到大排成双向链表。
2. 很明显中序遍历这个二叉搜索树能构成一个已排序的序列，然后构建双向链表即可。

代码

    ArrayList<Integer> AL = new ArrayList<>();
    public Node treeToDoublyList(Node root) {
    
        if(root==null) return null;
        //首先中序遍历这个root 找到排序后的数组
        DFS(root);
        //将arrayslist里的数构建成双向链表
        return createLink(AL);
    }
    public void DFS(Node root){
    
        if(root==null) return;
        DFS(root.left);
        AL.add(root.val);
        DFS(root.right);
    }
    public Node createLink(ArrayList a){
    
        //pre和next记录
        Node pre = null;
        Node next = null;
        //首尾节点记录
        Node head = null;
        Node tail = null;
        //必须得两轮才可以
        for(int i=a.size()-1;i>=0;i--){
    
            Node temp = new Node((Integer) a.get(i));
            if(i==a.size()-1){
    
                tail = temp; // 记录
                next = tail;
            }
            if(i!=a.size()-1){
    
                temp.right=next;
                next = temp;
                if(i==0) head=temp;
            }
        }
        if(head==null){
    
            //只有一个元素 其首尾都是自己
            tail.left = tail;
            tail.right = tail;
            return tail;
        }
        //开始连接head和tail 并且构建另一个方向的链表
        tail.right = head;
        head.left=tail;
        //从2开始构建
        Node temp = head.right;
        pre = head;
        while (tail.left==null){
    
            temp.left = pre;
            temp = temp.right;
            pre = pre.right;
        }
        return head;
    }