Jz36 binary search tree and bidirectional linked list

Catalog

Topic introduction

Introduction to the properties of binary search tree  

Topic analysis

How to solve the problem

Code implementation

---

Topic introduction

Topic link

JZ36 Binary search tree and double linked list

Title Description

Enter a binary search tree , The binary search tree is transformed into a sorted two-way linked list

Such as ：

Title Requirements and data scope

Data range ： Enter the number of nodes of the binary tree 0 <= n <= 1000, The value of each node in the binary tree 0 <= val <= 1000

requirement ： The space complexity is O(1), Time complexity O(n)

Title Precautions

Request cannot create new node , Only the nodes in the tree can be adjusted to point , The left pointer of the node in the tree points to the precursor , Right pointer to successor

Returns the pointer of the first node in the linked list

Function return TreeNode, There are left and right pointers , In fact, it can be regarded as a two-way linked list

No need to output bidirectional linked list , The program will automatically print out according to the return value

Introduction to the properties of binary search tree  

Binary search tree is also called binary sort tree , It has the following properties ：

• If its left subtree is not empty , Then the value of the left subtree node is less than the value of the root node
• If its right subtree is not empty , Then the value of the right subtree node is greater than the value of the root node
• Its left and right subtrees are also binary search trees

Topic analysis

The topic is to transform a binary search tree into an ordered two-way linked list , From the properties of the binary search tree above, it is not difficult to get , The result of traversing the middle order of the binary search tree is just in the order from small to large , The topic requires nodes left The pointer points to the front drive ,right The pointer points to the successor , So the idea of making the question is as follows ：

Link the nodes traversed in the middle order according to the requirements of the topic

How to solve the problem

Method 1

Drawing analysis process ：

 

 

The specific steps are as follows ：

1. Write a method of middle order traversal , Link node
2. The middle order traversal is implemented recursively , So define first on the outside of the method pre==null,pre Tag traversal root When the previous node
3. First recursively traverse the left subtree
4. let root.left == pre,if(pre != null) when , Give Way pre.right = root
5. Finally, recursively traverse the right subtree
6. The method given in the title should return to the first node , The first node is the leftmost node of the tree , First find the first node
7. If the tree is empty , return null, If it's not empty , If the left subtree of the root is not empty , Continue to find the leftmost node with the left subtree of the root as the tree
8. Call the above middle order traversal method
9. Return to the first node

Method 2

Because the topic gives the maximum number of nodes is 1000, And the space complexity is required to be O(1), So we can store the nodes traversed in the middle order into an array , This array new The size of the space is 1000, because 1000 Is the specific value , So the space complexity also meets O(1), Then traverse the array and link the nodes in the array

The specific steps are as follows ：

1. new Space for 1000 An array of nodes
2. Write a middle order traversal to store all the nodes in the tree in the array
3. In the method given in the title , Call the above method first , Store the nodes in the array
4. from index=0 Start traversing array , Give Way array[index+1].left = array[index],array[index].right = array[index+1]

Code implementation

Method one code

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    TreeNode pre = null;
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        root.left = pre;
        if(pre != null){
            pre.right = root;
        }
        pre = root;
        inOrder(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        inOrder(pRootOfTree);
        return head;
    }
}

Method 2 code

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    TreeNode[] array = new TreeNode[1000];
    int i = 0;
    public void inOrder(TreeNode root){
        if(root != null){
            inOrder(root.left);
            array[i++] = root;
            inOrder(root.right);
        }
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        inOrder(pRootOfTree);
        int index = 0;
        while(array[index+1] != null){
            array[index].right = array[index+1];
            array[index+1].left = array[index];
            index++;
        }
        return array[0];
    }
}