题目

思路

1. Read the topic for a long time…The meaning should be that there is a complete binary search tree,Arranged in a doubly linked list from smallest to largest.
2. It is obvious that an inorder traversal of this binary search tree can form a sorted sequence,Then build a doubly linked list.

代码

    ArrayList<Integer> AL = new ArrayList<>();
    public Node treeToDoublyList(Node root) {
    
        if(root==null) return null;
        //First traverse this in-orderroot Find the sorted array
        DFS(root);
        //将arrayslistThe numbers are constructed as a doubly linked list
        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;
        //head and tail node records
        Node head = null;
        Node tail = null;
        //It takes two rounds
        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){
    
            //只有一个元素 Its beginning and end are itself
            tail.left = tail;
            tail.right = tail;
            return tail;
        }
        //开始连接head和tail And build a linked list in the other direction
        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;
    }