[leetcode 108] Convert Sorted Array to Binary Search Tree


質問リンク

マイロジック


まず正解の論理と同じです.ただし、エラー処理によりコードが複雑になり、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を抽出します.