“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022.”
36. Binary search tree with bidirectional linked list
Force link topic linked list
Enter a binary search tree and convert the binary search tree into a sorted circular bidirectional list. You cannot create any new nodes. You can only adjust the Pointers to nodes in the tree.
Each node in a linked list has a precursor and a successor pointer. For a bidirectional circular list, the first node is preceded by the last node, and the last node is succeeded by the first node.
Ideas:
We first throw out the conclusion that the middle-order traversal of a binary search tree results in an increased order. According to the requirements of the topic, the binary search tree needs to be converted into a sorted circular bidirectional list, so the binary search tree needs to be traversed in order.
In the sequence traversal
/ * * *@param {Node} root
* @return {Node}* /
const treeToDoublyList = (root) = > {
let pre = null; // Initializes the precursor node
let head = null; // Initialize the header node
const dfs = (cur) = > {
if(! cur)return;
dfs(cur.left);
if (pre) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
if(! root)return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
};
Copy the code- Time complexity O(n).
- Space complexity O(n).
Analysis:
The code is divided into three parts. The first part is middle order traversal binary search tree. The second part is a bidirectional linked list; The third part is to process a circular linked list. Let’s analyze it step by step.
First we declare two Pointers to the precursor node of the current node and the head node of the current list. The precursor node is recorded because we want to process it into a bidirectional list, and the header node is recorded because the final result needs to return the head node of the list.
Now let’s look at sequential traversal. Since it’s a recursion, the first thing we need to do is write the termination condition for the recursion. The terminating condition here is that the node is null. Then we recurse to the left child, process the current node, recurse to the right child. The logic for processing the current node is to process it as a bidirectional linked list.
Now let’s do a bidirectional linked list. Assign the current node to the right pointer of the precursor node if the precursor node exists (in this case, the previous traversal node after the backtrace). If the precursor node does not exist, it means that the current node is the first node, so it is assigned to the head node. Assigns the precursor node to the left pointer of the current node, regardless of whether the precursor node exists. So far, we’ve had a two-way relationship with the Pre and CUR. Finally, assigning the current node to the precursor node means that the precursor node moves back one step, waiting for the next recursive call.
Finally, let’s do a circular linked list. This is essentially the logic of the pivot function. If the binary search tree is empty, null is returned. And then we recurse the binary tree, and we turn it into a bidirectional list. Once the recursion is over, the bidirectional list is done. Head points to the head node and pre points to the tail node. As long as we establish a bidirectional relationship between Head and Pre, we can form a circular bidirectional linked list. We simply assign the tail node to the left pointer of the head node and the head node to the right pointer of the tail node. So you can connect the end to the end.
conclusion
The problem is to form an increased list through middle order traversal. Process the list as a bidirectional list inside the middle order traversal. Finally, end to end to form a circular bidirectional linked list.
In terms of complexity, middle-order traversal requires access to all nodes. So the time is order n. In the worst case, the binary tree degenerates into a linked list, requiring O(n) stack space. So the space complexity is order n.