109. Convert Sorted List to Binary Search Tree

leetcode medium

#array#csharp#leetcode#linked-list#medium#recursion#search#sort#tree#two-pointers

Task

Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска.

Пример:

Input: head = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]

Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

C# solution

matched/original

public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        if (head == null)
            return null;
        ListNode mid = FindMiddleElement(head);
        TreeNode node = new TreeNode(mid.val);
        if (head == mid)
            return node;
        node.left = this.SortedListToBST(head);
        node.right = this.SortedListToBST(mid.next);
        return node;
    }
    private ListNode FindMiddleElement(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;
        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        if (prevPtr != null)
            prevPtr.next = null;
        return slowPtr;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public TreeNode SortedListToBST(ListNode head) {
        if (head == null)
            return null;
        ListNode mid = FindMiddleElement(head);
        TreeNode node = new TreeNode(mid.val);
        if (head == mid)
            return node;
        node.left = this.SortedListToBST(head);
        node.right = this.SortedListToBST(mid.next);
        return node;
    }
    private ListNode FindMiddleElement(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;
        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        if (prevPtr != null)
            prevPtr.next = null;
        return slowPtr;
    }
}

Java solution

matched/original

class Solution {
    private ListNode findMiddleElement(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;

        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        if (prevPtr != null) {
            prevPtr.next = null;
        }

        return slowPtr;
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode mid = this.findMiddleElement(head);
        TreeNode node = new TreeNode(mid.val);

        if (head == mid) {
            return node;
        }

        node.left = this.sortedListToBST(head);
        node.right = this.sortedListToBST(mid.next);
        return node;
    }
}

JavaScript solution

matched/original

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
}

var sortedListToBST = function(head) {
    if (!head) return null;
    var mid = findMiddleElement(head);
    var node = new TreeNode(mid.val);
    if (head === mid) return node;
    node.left = sortedListToBST(head);
    node.right = sortedListToBST(mid.next);
    return node;
};

var findMiddleElement = function(head) {
    var prevPtr = null;
    var slowPtr = head;
    var fastPtr = head;
    while (fastPtr && fastPtr.next) {
        prevPtr = slowPtr;
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next.next;
    }
    if (prevPtr != null) prevPtr.next = null;
    return slowPtr;
};

Python solution

matched/original

class Solution:

    def findMiddle(self, head: ListNode) -> ListNode:
        prevPtr = None
        slowPtr = head
        fastPtr = head
        while fastPtr and fastPtr.next:
            prevPtr = slowPtr
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
        if prevPtr:
            prevPtr.next = None
        return slowPtr

    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        mid = self.findMiddle(head)
        node = TreeNode(mid.val)
        if head == mid:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

Go solution

matched/original

type ListNode struct {
    Val  int
    Next *ListNode
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }
    mid := findMiddleElement(head)
    node := &TreeNode{
        Val: mid.Val,
    }
    if head == mid {
        return node
    }
    node.Left = sortedListToBST(head)
    node.Right = sortedListToBST(mid.Next)
    return node
}

func findMiddleElement(head *ListNode) *ListNode {
    var prevPtr *ListNode = nil
    slowPtr := head
    fastPtr := head
    for fastPtr != nil && fastPtr.Next != nil {
        prevPtr = slowPtr
        slowPtr = slowPtr.Next
        fastPtr = fastPtr.Next.Next
    }
    if prevPtr != nil {
        prevPtr.Next = nil
    }
    return slowPtr
}

Explanation

Algorithm

1️⃣

Поскольку нам дан односвязный список, а не массив, у нас нет прямого доступа к элементам списка по индексам. Нам нужно определить средний элемент односвязного списка. Мы можем использовать подход с двумя указателями для нахождения среднего элемента списка. В основном, у нас есть два указателя: slow_ptr и fast_ptr. slow_ptr перемещается на один узел за раз, тогда как fast_ptr перемещается на два узла за раз. К тому времени, как fast_ptr достигнет конца списка, slow_ptr окажется в середине списка. Для списка с четным количеством элементов любой из двух средних элементов может стать корнем BST.

2️⃣

Как только мы находим средний элемент списка, мы отсоединяем часть списка слева от среднего элемента. Мы делаем это, сохраняя prev_ptr, который указывает на узел перед slow_ptr, т.е. prev_ptr.next = slow_ptr. Для отсоединения левой части мы просто делаем prev_ptr.next = None.

3️⃣

Для создания сбалансированного по высоте BST нам нужно передать только голову связанного списка в функцию, которая преобразует его в BST. Таким образом, мы рекурсивно работаем с левой половиной списка, передавая оригинальную голову списка, и с правой половиной, передавая slow_ptr.next в качестве головы.

😎