【LeetCode】 108. Convert Sorted Array to Binary Search Tree 解答・解説【Python】

この記事は約3分で読めます。

 

問題

原文

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

※A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

Example 1:

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:

Example 2:

Input: nums = [1,3]

Output: [3,1]

Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.

 

内容

昇順に並べられた数値型配列numsが与えられるので、高さが調整された二分探索木に変換してください。

※高さが調整された二分探索木とは、全てのノードにおいて左右の子ノードの深さが1以上の差を持たないものをいいます。

制約

・numsの要素数は1~10^4

・numsの各要素の値は-10^4~10^4

・numsは単調増加

 

※正しくない可能性があります。

方針

・以下の処理を関数にして再帰的に行います。

→numsに要素があれば、その中央の要素を親ノードにして二分木を作成

→numsの左半分と右半分の子ノードでそれぞれここまでの処理を関数として再度呼び出す

解答

解答1:

木が埋まる流れは以下のようなイメージで捉えています。

※・→numsの各要素(まだ木に変換されていない)

○→木に変換されたnumsの各要素

実行前 ・・・・・・・

※中央の要素から木に変換していく

1回目 ・・・○・・・

※中央の要素を根ノードとして木に変換

2回目 ・○・○・○・

※中央の要素から見て左半分の要素内において、再度中央の要素を親ノードとして木に変換

3回目  ○○○○○○○

※上記処理を再度行う

 

ちなみに、今気づいたのですが、もともと問題の制約として昇順にnumsが並べられているので、途中のソートは不要ですね。Leetcodeでsubmitしたときに、他の解答と比べてかなり遅かったのですが、並べ替え処理があることが理由かと思います。

補足・参考・感想

時間・空間計算量の考え方が現状全く身についていないので、問題の解法を考えながら計算量も考えられるようになりたいです。

 

 

前:101. Symmetric Tree

次:110. Balanced Binary Tree

LeetCode 解答・解説記事一覧

コメント