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

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

問題

原文

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 <= 10⁴

-10⁴ <= nums[i] <= 10⁴

nums is sorted in a strictly increasing order.

内容

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

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

制約

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

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

・numsは単調増加

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

方針

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

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

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

解答

解答1：

#recursive       
#配列numsの中央の要素を根ノードにし、その左半分と右半分でそれぞれ再度sortedArrayToBST関数を呼び出す
#2回目以降の処理では、1回目の左半分・右半分でそれぞれ中央の要素を親ノードにし、再度左半分と右半分でそれぞれ再度sortedArrayToBST関数を呼び出す。以降繰り返し
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        #再帰的に呼び出し続けるといずれnumsの端にたどり着くのでNoneと返す。(この部分がないとIndexErrorになる)
        if not nums:
            return None
        #端の要素に到達していない間はこちらの処理を行う
        else:
            #numsをソート
            nums = sorted(nums)
            #numsの中央の要素をmiddleに代入
            middle = len(nums)//2
            #numsの中央の要素を根ノードとしてTreeNodeクラスをインスタンス化したrootを作成
            root = TreeNode(nums[middle])
            #これは解答とは無関係
            print(root)
            #numsの左半分の要素を引数にして、rootの左側の子ノードで上記と同じ処理を行う
            root.left = self.sortedArrayToBST(nums[:middle])
            #numsの右半分の要素を引数にして、rootの右側の子ノードで上記と同じ処理を行う
            root.right = self.sortedArrayToBST(nums[middle+1:])
            #これは解答とは無関係
            print(root,nums)
        return root

#recursive

#配列numsの中央の要素を根ノードにし、その左半分と右半分でそれぞれ再度sortedArrayToBST関数を呼び出す

#2回目以降の処理では、1回目の左半分・右半分でそれぞれ中央の要素を親ノードにし、再度左半分と右半分でそれぞれ再度sortedArrayToBST関数を呼び出す。以降繰り返し

class Solution:

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

#再帰的に呼び出し続けるといずれnumsの端にたどり着くのでNoneと返す。(この部分がないとIndexErrorになる)

if not nums:

return None

#端の要素に到達していない間はこちらの処理を行う

else:

#numsをソート

nums = sorted(nums)

#numsの中央の要素をmiddleに代入

middle = len(nums)//2

#numsの中央の要素を根ノードとしてTreeNodeクラスをインスタンス化したrootを作成

root = TreeNode(nums[middle])

#これは解答とは無関係

print(root)

#numsの左半分の要素を引数にして、rootの左側の子ノードで上記と同じ処理を行う

root.left = self.sortedArrayToBST(nums[:middle])

#numsの右半分の要素を引数にして、rootの右側の子ノードで上記と同じ処理を行う

root.right = self.sortedArrayToBST(nums[middle+1:])

#これは解答とは無関係

print(root,nums)

return root

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

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

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

実行前　・・・・・・・

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

1回目　・・・○・・・

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

2回目　・○・○・○・

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

3回目　 ○○○○○○○

※上記処理を再度行う

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

補足・参考・感想

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

前：101. Symmetric Tree

次：110. Balanced Binary Tree

LeetCode 解答・解説記事一覧