🐕

108. Convert Sorted Array to Binary Search Tree

に公開
PHP
TypeScript
LeetCode
tech

昇順にソートされた整数配列 nums が与えられたとき、それを高さバランスの取れた二分探索木（BST）に変換します。

例1:

入力:

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

出力:

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

説明:
以下の形も受け入れ可能です:

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

例2:

入力:

nums = [1, 3]

出力:

[3, 1]

説明:
以下の形も受け入れ可能です:

[1, null, 3] および [3, 1]

制約:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums は厳密に増加する順序でソートされている。

  • ソートされた配列の中央を根ノードとして選ぶ

  • 左右部分木を再帰的に生成

    • 左部分木は中央より左の部分を、右部分木は中央より右の部分を再帰的に処理。

  • 再帰終了条件

    • 開始位置が終了位置を超えた場合は null を返して部分木の終端とする。

Discussion