[flax high frequency question] leetcode 426 Convert binary search tree to sorted double linked list

Title Description & link

Leetcode 426 :  take BST The structure is transformed into a double linked list structure , Make each node connect its predecessor node and successor node , And head , The last two nodes should also be connected . No extra space required

Topic ideas

I'll give you a compliment on this question , Let me traverse the middle order DFS The template has a deeper understanding . First of all, what if you can open additional space ？ Think that there is a hidden property of order traversal in binary trees ： In the middle order traversal, the point on the current node is the precursor node , The next point is the successor node . Then you can put BST The structure is traversed in medium order , Save and traverse the array so that each point is connected to the left and right .

What should I do if I don't use extra space . Let's take a look first BST Middle order traversal template , as follows

 private void dfs(Node root) {
        if(root==null) return;
        
        dfs(root.left);
        //  The following is the processing area  -  Displays the current node 
        System.out.println(root.val);
        // 
        dfs(root.right);
    }

We can start processing every time out recursion , Connect the precursor node with the current node , Then connect the head and tail nodes . The whole idea , First, you need to save the header , The last two nodes , First entry in recursion " Processing area " Is the first node , The last entry in recursion " Processing area " It's the last node . How to get the precursor node in recursion , Define a global variable , Save the current node after each processing logic in the processing area , So the next time you enter the processing area , The saved node is the precursor node of this node .

Processing area logic , Connect the current node with the predecessor node , The overall code is as follows ：

/*
// 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 {
    Node first = null;
    Node last = null;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        // The middle order traverses the previous node and the next node 
        dfs(root);
        first.left = last;
        last.right = first;
        
        return first;
    }
    
    private void dfs(Node root) {
        if(root==null) return;
        
        dfs(root.left);
        // do something
        //  The first point entering the processing area must be the first point ( Leftmost point )
        if(last!=null) {
            //  Somewhere in the middle 
            //  The first point is last 
            last.right = root;
            root.left = last;
        }
        if(first==null) first = root;
        last = root; // last  Keep updating until the last entry, that is, the rightmost point 
        dfs(root.right);
    }
}

Time complexity ：; Spatial complexity ：  Recursion depth .