Viiisit [LeetCode] - 108. Convert Sorted Array to Binary Search Tree

keep learning, keep coding!

Problem - Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

翻譯蒟蒻

將一個已經按升序排列的整數陣列轉換成一個高度平衡的二元搜尋樹（BST）。

• 二元搜尋樹（BST）：
  二元搜尋樹是一種樹狀結構，其中每個節點最多有兩個子節點，且左子樹的所有節點的值都小於等於該節點的值，右子樹的所有節點的值都大於該節點的值。這種特性使得在搜尋、插入和刪除元素時，可以以較高效的方式進行。

• 高度平衡的二元搜尋樹：
  高度平衡的二元搜尋樹是指樹中的每個節點的兩個子樹的深度差不超過一。這確保樹的高度相對較小，提高了搜索、插入和刪除操作的效率，因為不會發生樹過度不平衡的情況。

---

• Example 1:

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

• Example 2:

  Input: nums = [1,3]
  Output: [3,1]

---

先找出樹的根節點，由於陣列已經按升序排列，可以選擇陣列的中間元素作為樹的根節點，這樣可以確保左右子樹的大小相對平衡，接著分別遞迴處理左右子樹。

---

Solution - JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
  if (nums.length === 0) return null;
  
  // 找到陣列的中間索引  
  let mid = Math.floor(nums.length / 2);
  let root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
};

Solution - Ruby

def sorted_array_to_bst(nums)
  return nil if nums.empty?
  return TreeNode.new(nums[0]) if nums.size == 1
  mid = nums.size / 2
  root = TreeNode.new(nums[mid])
  root.left = sorted_array_to_bst(nums[0...mid])
  root.right = sorted_array_to_bst(nums[mid+1..-1])
  return root
end

Solution - PHP

function sortedArrayToBST($nums) {
  if (count($nums) === 0) {
      return null;
  }
  $mid = floor(count($nums) / 2);
  $node = new TreeNode($nums[$mid]);
  $node->left = $this->sortedArrayToBST(array_slice($nums, 0, $mid));
  $node->right = $this->sortedArrayToBST(array_slice($nums, $mid + 1));
  return $node;
}

LeetCode 傳送門 - Convert Sorted Array to Binary Search Tree