[daily question 1] binary search tree and bidirectional linked list

Title source ： Cattle from ：BM30 Binary search tree and double linked list

Title Description

Enter a tree Binary search tree , Transform the binary search tree 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 1000$, The value of each node in the binary tree $0\le val\le 1000$
requirement ： Spatial complexity $O(1)$（ That is, operate on the original tree ）, Time complexity $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 .

Example

 Input ：
{
    10,6,14,4,8,12,16}
 Return value ：
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
 explain ：
 Enter the binary tree in the problem surface diagram , When outputting, return the head node of the bidirectional linked list .  

Example

 Input ：
{
    5,4,#,3,#,2,#,1}
 Return value ：
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
 explain ：
                    5
                  /
                4
              /
            3
          /
        2
      /
    1
 The shape of the tree is shown in the figure above        

Their thinking

Recursive middle order traversal

---

Knowledge point 1： Binary tree recursion
Recursion is a method in which a procedure or function directly or indirectly calls itself in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve . So recursive process , The most important thing is to see if the original problem can be broken down into smaller sub problems , This is the key to using recursion .

And the recursion of binary tree , The left subtree of a node 、 The right subtree is regarded as a complete tree , Then the access or operation of the subtree is the sub problem of the access or operation of the original tree , So you can call your own function and keep entering the subtree .

Knowledge point 2： Binary search tree
Binary search tree is a special binary tree , Its value of each node is greater than its left child node , And greater than the node value of all left subtrees , Smaller than its right child node , And less than the node value of all right subtrees . Therefore, binary search tree is a kind of Sort structure .

---

Ideas

The leftmost element of the binary search tree must be the smallest , The rightmost element must be the largest , accord with “ Left middle right ” Characteristics of , Therefore, the middle order traversal of binary search tree is an increasing sequence , As long as it is traversed in order, it can be assembled into an incremental two-way linked list
specific working means

1. Create two pointers , A chain header that points to the requirements of the topic （head）, A point to the previous node of the current traversal （pre）.
2. First recurse to the leftmost , initialization head and pre
3. Then deal with the intermediate root node , Connect accordingly pre With the current node , Update after connecting pre Is the current node
4. Finally, recursively enter the right subtree , To continue processing
5. The recursive exit returns if the node is empty

Code

Java

public class Solution{
    
	//  Return the first pointer , That's the minimum , First set it as null
	public TreeNode head = null;
	//  Traverse the previous bit of the current value in the middle order , The initial value is the minimum value , It is also defined as null
	public TreeNode prev = null;
	public TreeNode Convert(TreeNode pRootOfTree){
    
		if(pRootOfTree == null)
			// In the sequence traversal , The leaf node is empty , Then return to 
			return null;
		//  First recursive left subtree 
		Convert(pRootOfTree.left);
		//  Find the minimum , initialization head and prev
		if(prev==null){
    
			head = pRootOfTree;
			prev = pRootOfTree;
		}else{
    
			pre.right = pRootOfTree;
			pRootOfTree.left = pre;
			pre = pRootOfTree;
		}
		//  Traversal right subtree 
		Convert(pRootOfTree.right);
		return head;
	}
}

Python3

# -*- coding: utf-8 -*-#

# ----------------------------------------------
# Name: BM30.py
# Description:  Binary search tree and double linked list 
# Author: PANG
# Date: 2022/7/11
# ----------------------------------------------
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    head = None
    pre = None

    def Convert(self, pRootOfTree):
        if pRootOfTree is None:
            return None
        #  Traverse to the leftmost minimum 
        self.Convert(pRootOfTree.left)
        #  Find the minimum , initialization head and pre
        if not self.pre:
            self.head = pRootOfTree
            self.pre = pRootOfTree
        else:
            self.pre.right = pRootOfTree
            pRootOfTree.left = self.pre
            self.pre = pRootOfTree
        #  Traverse to the right subtree 
        self.Convert(pRootOfTree.right)
        return self.head

Complexity analysis

• Time complexity ：$O(n)$, among n Is the number of binary tree nodes , Traverse all nodes in middle order ;
• Spatial complexity ：$O(n)$, The maximum space required for the recursive stack