Leetcode exercise - Sword finger offer 36 Binary search tree and bidirectional linked list

1. Title Description

The finger of the sword Offer 36. Binary search tree and double linked list

Enter a binary search tree , The binary search tree is transformed into a sorted circular bidirectional linked list . It is required that no new nodes can be created , You can only adjust the direction of the node pointer in the tree .

In order for you to better understand the problem , Take the following binary search tree as an example ：

We hope to transform this binary search tree into a two-way circular linked list . Each node in the linked list has a precursor and successor pointer . For two-way circular linked list , The precursor of the first node is the last node , The last node is followed by the first node .

The following figure shows the linked list transformed from the above binary search tree .“head” Indicates the node with the smallest element in the linked list .

Specially , We want to be able to complete the conversion in place . When the conversion is complete , The left pointer of the node in the tree needs to point to the precursor , The right pointer of the node in the tree needs to point to the successor . You also need to return the pointer of the first node in the linked list .

2.1 Their thinking

Given a binary search tree , And it is required to turn it into a ordered two-way linked list on the basis of the original node , And return the node with the smallest value . According to the meaning of the question, you need to complete two steps ： The first step is to sort the nodes of the binary search tree , The second step is to connect the nodes into a two-way linked list . Because the title is given as a binary search tree , Therefore, we can get the nodes from small to large by traversing the binary search tree , Using this property, we can complete the first step , Traverse and put the node in the queue , Used for assembling bidirectional linked list .

Get the ordered node queue, and then start to assemble the bidirectional linked list , The first node of the queue is the head node that needs to be returned , After the node left Point to the previous node of the current node in the queue , right Just think of the next node of the current node in the queue , Until the queue is empty . At this time, connect the head node and the tail node to complete the problem requirements .

Take the example of topic presentation , First, do the middle order traversal , Get the node queue [1, 2, 3, 4, 5]

Then get the header node from the queue , Then traverse the queue in turn , Set the previous node pre Of right Point to the current node popped out of the queue curr, And then the current node's left Point to the previous node . After this operation, you will pre Point to the current node , Continue to facilitate the queue , Until all the nodes in the queue pop up .

The last step is to connect the ending nodes , At this point, complete the assembly of the two-way circular linked list .

2.2 Code

class Solution {
    
    Queue<Node> queue = new LinkedList<>();

    public Node treeToDoublyList(Node root) {
    
        if (root == null) {
    
            return null;
        }
        process(root);
        //  Pop up the team head node as the head node , And use  pre  Point to previous node 
        Node head = queue.poll();
        Node pre = head;
        while (!queue.isEmpty()) {
    
            //  Pop the queue header from the queue , Then connect the previous node with the current node 
            Node curr = queue.poll();
            pre.right = curr;
            curr.left = pre;
            pre = curr;
        }
        //  After the queue is ejected, make a closing connection 
        pre.right = head;
        head.left = pre;
        return head;
    }

    public void process(Node root) {
    
        if (root == null) {
    
            return;
        }
        process(root.left);
        //  In the sequence traversal , Put the node in the queue 
        queue.offer(root);
        process(root.right);
    }
}

2.3 test result

Pass the test

3. summary

• Using the ergodic property of the binary search tree to obtain the sorted node queue
• Then use the node queue to assemble the bidirectional circular linked list