Niu Ke's questions -- binary search tree and bidirectional linked list

Topic link ： Binary search tree and double linked list

Title Description

Enter a binary search tree , The binary search tree is transformed into a sorted double linked list . As shown in the figure below

Data range ： Enter the number of nodes of the binary tree 0 \le n \le 10000≤n≤1000, The value of each node in the binary tree 0\le val \le 10000≤val≤1000
requirement ： Spatial complexity O(1)O(1)（ That is, operate on the original tree ）, Time complexity O(n)O(n)

Be careful :
1. It is required that no new nodes can be created , You can only adjust the direction of the node pointer in the tree . 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
2. Returns the pointer of the first node in the linked list
3. Function return TreeNode, There are left and right pointers , In fact, it can be regarded as a data structure of a two-way linked list
4. You don't have to output a two-way linked list , The program will automatically print out according to your return value
Input description ：
The root node of a binary tree
Return value description ：
One of the head nodes of the two-way linked list .

Topic analysis

The problem is to change a binary search tree structure into a two-way linked list , The left pointer points to the front drive , Right pointer to successor . At the same time, the two-way linked list is required to be orderly . One of the characteristics of binary search tree is that if you traverse the binary search tree in middle order, you can get an orderly arrangement . You must modify the original tree and cannot create new nodes . So how to modify it . According to the characteristics of middle order traversal , You can set a prev The pointer , Start set to empty , In fact, it is the precursor node of each node , In this way, during the middle order traversal , The linked list can be connected before and after , In this way, the bidirectional linked list required in the title can be realized . Finally, according to the requirements of the topic , Return the head node of the linked list . The code implementation is as follows ：

	cur->left = prev;
	if (prev)
	{
    
		prev->right = cur;
	}
	prev = cur;

Code implementation

void InOrder(TreeNode* cur, TreeNode*& prev)// In the sequence traversal 
{
    
	if (cur == nullptr)// If it is empty, it will return to 
	{
    
		return;
	}
	InOrder(cur->left, prev);
	cur->left = prev;
	if (prev)
	{
    
		prev->right = cur;
	}
	prev = cur;
	InOrder(cur->right, prev);
}



TreeNode* Convert(TreeNode* pRootOfTree)
{
    
	if (pRootOfTree == nullptr)
	{
    
		return nullptr;
	}
	TreeNode* prev = nullptr;
	TreeNode* cur = pRootOfTree;
	InOrder(cur, prev);
	TreeNode* ret = pRootOfTree;
	while (ret->left)
	{
    
		ret = ret->left;
	}
	return ret;
}