“This is the 28th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The binary search tree of ordered linked list transformation is shown below:

Given a single linked list whose elements are sorted in ascending order, convert it into a highly balanced binary search tree.

In this case, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is less than 1.

Example:

Given an ordered list: [-10, -3, 0, 5, 9], a possible answer is [0, -3, 9, -10, NULL, 5], which can represent the following highly balanced binary search tree: 0 / \ -3 9 / / -10 5Copy the code

A, thinking

This problem is very similar to the previous problem (108) – converting an ordered array to a binary search tree. The only difference is that an ascending array is replaced by an ascending list.

Because the absolute value of the height difference between the left and right subtrees is no more than 1, the root node in the ascending array takes the middle value as the root node. But there’s no way to get the middle value directly in the list, so I started by walking through the list, turning it into an ArrayList.

Solution 1: first turnList

  1. Iterate through the list and convert toList
  2. Take the current interval each timeleft ~ rightIs used as the root node

The pseudocode is shown below:

public TreeNode sortedListToBST(ListNode head) {
    List<Integer> list = linkList2ArrayList(head); / / to the List
    return dfs(list, 0, list.size()-1);
}

public TreeNode dfs(List<Integer> list, int left, int right){
    if (left > right)
        return null;
    int mid = (left+right)/2; // take the middle value
    TreeNode root = new TreeNode(list.get(mid));
    root.left = dfs(list, left, mid-1);
    root.right = dfs(list, mid+1, right);
    return root;
}
Copy the code

When I implemented it this way, THE beat rate was low (about 28%). So I looked at the official solution and found that the official use of fast and slow Pointers to find the middle position, so as to avoid traversing the entire list.

Solution two: fast and slow pointer

Let’s start by illustrating how to use the fast and slow Pointers to find the middle of the list.

If you have a linked list 1-> 2 -> 3 -> 4 -> 5 -> 6 -> 7, how do you find the middle element 4?

For arrays, we know the left and right of arrays (right means arr. Lenght). So mid is equal to (left+right)/2, and the middle element is arr[mid]. Since we don’t know where the right boundary is in the list, we can make both Pointers fast and slow start from left. For every step slow takes, FAST takes two steps until fast reaches the end of the list. Because slow has traveled half as far as Fast when fast has gone through the list, slow is now pointing to the middle of the list

  1. slow 和 fastPoint to the leftmost part of the list, the head

  1. fastTake two steps,slowWalk the one step

  1. fastTwo more steps,slowWalk the one step

  1. fastTwo more steps,slowWalk the one step. At this timefastThe end,slowIt points to the middle element4

After the above illustration, we know how to find the middle element in the linked list. Then the rest of the steps will be easy. All we need to do is update the left and right boundaries of the list and find the middle of the left and right boundaries as the root node

Second, the implementation

The implementation code

Here is the implementation code for solution 2, notice that right=null at the beginning

public TreeNode sortedListToBST(ListNode head) { return buildTree(head, null); } public TreeNode buildTree(ListNode left, ListNode right) { if (left == right) { return null; } ListNode mid = getMid(left, right); TreeNode root = new TreeNode(mid.val); root.left = buildTree(left, mid); root.right = buildTree(mid.next, right); return root; } public ListNode getMid(ListNode left, ListNode right) {ListNode fast = left; ListNode slow = left; while (fast ! = right && fast.next ! = right) { fast = fast.next; fast = fast.next; slow = slow.next; } return slow; }Copy the code

The test code

    public static void main(String[] args) {
        ListNode listNode = new ListNode(-10.new ListNode(-3.new ListNode(0.new ListNode(5.new ListNode(9)))));
        TreeNode treeNode = new Number109().sortedListToBST(listNode);
        System.out.println("debug");
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section