[leetcode 108] Convert Sorted Array to Binary Search Tree
6831 ワード
質問リンク
マイロジック
マイロジック
まず正解の論理と同じです.ただし、エラー処理によりコードが複雑になり、C++スタイルになります.
最初はリストの中間値を求め、それをツリーのルートに変え、リストを最初の要素からループし、ルート要素からBSTで値を挿入してから間違っています.
そして熟考を経て、正しい答えの論理が得られた.木の高さ差は最大1にしかならないので、子を求める木の親ノードが重要です.このようにしてこそ、左右に均一に元素を加える条件を作ることができる.
例を表示して規則性を検索[..prev...,parent,..next...]リストがそうである場合、parentを除いてprevのすべての要素では、位置の中間値は常に親ノードの左ノードであり、nextの中間値は親ノードの右ノードである.要素長の中間値にある要素が親ノードとなっていることが判明した後,道路ごとに左,右の2つの部分に分けて再帰的に解くことにした. def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
left = 0
right = len(nums)-1
def solution(left, right):
if left < 0 or right < 0 or left > len(nums) or right > len(nums):
return None
if left > right:
return None
if left == right :
return TreeNode(nums[left])
mid = (left + right) // 2
parent = TreeNode(nums[mid])
parent.left = solution(left,mid-1)
parent.right = solution(mid+1,right)
return parent
エラー処理でコードが乱れている
答えのロジック
本の中でパイソンニックはリストの線で同じ論理を体現している. def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
mid = len(nums)//2
parent = TreeNode(nums[mid])
parent.left = self.sortedArrayToBST(nums[:mid])
parent.right = self.sortedArrayToBST(nums[mid+1:])
return parent
リストインデックスを使用して、パラメータに左、右を渡すには、リスト[:mid]、list[mid+1:]を使用します.
リストのスムージングを使用する場合、インデックスが範囲外の場合、
空のリストを返すので、エラー処理でも簡単です.
後で左、右などのバイナリ検索を行うときは、必ず頭の中からlist sleingを抽出します.
Reference
この問題について([leetcode 108] Convert Sorted Array to Binary Search Tree), 我々は、より多くの情報をここで見つけました
https://velog.io/@wlgns2223/leetcode-108-Convert-Sorted-Array-to-Binary-Search-Tree
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
left = 0
right = len(nums)-1
def solution(left, right):
if left < 0 or right < 0 or left > len(nums) or right > len(nums):
return None
if left > right:
return None
if left == right :
return TreeNode(nums[left])
mid = (left + right) // 2
parent = TreeNode(nums[mid])
parent.left = solution(left,mid-1)
parent.right = solution(mid+1,right)
return parent
本の中でパイソンニックはリストの線で同じ論理を体現している.
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
mid = len(nums)//2
parent = TreeNode(nums[mid])
parent.left = self.sortedArrayToBST(nums[:mid])
parent.right = self.sortedArrayToBST(nums[mid+1:])
return parent
リストインデックスを使用して、パラメータに左、右を渡すには、リスト[:mid]、list[mid+1:]を使用します.リストのスムージングを使用する場合、インデックスが範囲外の場合、
空のリストを返すので、エラー処理でも簡単です.
後で左、右などのバイナリ検索を行うときは、必ず頭の中からlist sleingを抽出します.
Reference
この問題について([leetcode 108] Convert Sorted Array to Binary Search Tree), 我々は、より多くの情報をここで見つけました https://velog.io/@wlgns2223/leetcode-108-Convert-Sorted-Array-to-Binary-Search-Treeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol