問題
原文
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#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したときに、他の解答と比べてかなり遅かったのですが、並べ替え処理があることが理由かと思います。
補足・参考・感想
時間・空間計算量の考え方が現状全く身についていないので、問題の解法を考えながら計算量も考えられるようになりたいです。
コメント