108. Convert Sorted Array to Binary Search Tree

leetcode easy

#array#csharp#easy#leetcode#recursion#search#sort#tree#two-pointers

Task

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

Пример:

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

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

Explanation: [0,-10,5,null,-3,null,9] is also accepted:

C# solution

matched/original

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.Length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(nums, left, p - 1);
        root.right = helper(nums, p + 1, right);
        return root;
    }
}

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 SortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
    public TreeNode helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(nums, left, p - 1);
        root.right = helper(nums, p + 1, right);
        return root;
    }
}

Java solution

matched/original

class Solution {
    int[] nums;

    public TreeNode helper(int left, int right) {
        if (left > right) return null;

        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(left, p - 1);
        root.right = helper(p + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return helper(0, nums.length - 1);
    }
}

JavaScript solution

matched/original

var sortedArrayToBST = function (nums) {
    return helper(nums, 0, nums.length - 1);
};
var helper = function (nums, left, right) {
    if (left > right) {
        return null;
    }
    var p = Math.floor((left + right) / 2);
    var root = new TreeNode(nums[p], null, null);
    root.left = helper(nums, left, p - 1);
    root.right = helper(nums, p + 1, right);
    return root;
};

Python solution

matched/original

class Solution:
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None

            p = (left + right) // 2
            root = TreeNode(nums[p])
            root.left = helper(left, p - 1)
            root.right = helper(p + 1, right)
            return root

        return helper(0, len(nums) - 1)

Go solution

matched/original

func sortedArrayToBST(nums []int) *TreeNode {
    return helper(nums, 0, len(nums)-1)
}

func helper(nums []int, left int, right int) *TreeNode {
    if left > right {
        return nil
    }
    p := (left + right) / 2
    root := &TreeNode{Val: nums[p]}
    root.Left = helper(nums, left, p-1)
    root.Right = helper(nums, p+1, right)
    return root
}

Explanation

Algorithm

1️⃣

Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.

Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2️⃣

Выбор корня и разделение массива:

Выберите элемент в середине для корня: p = (left + right) // 2.

Инициализируйте корень: root = TreeNode(nums[p]).

3️⃣

Рекурсивное построение поддеревьев:

Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1).

Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).

В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎