나의 논리
우선 정답의 논리와는 똑같다. 다만 에러처리로 인해 코드가 복잡하며 여전히 C++ 스타일인것 같다.
처음에는 리스트의 중간값을 구한뒤 트리의 루트로 만든 후 리스트를 첫번째 원소부터 순회하며 그냥 루트에서부터 값을 BST방식으로 삽입하는 걸로 했다가 틀렸다.
그리고 곰곰히 다시 생각 해본 결과 정답논리를 얻게 되었다. 트리의 높이차가 최대 1만 나야하므로 서브트리의 부모노드를 구하는것이 중요하다. 그래야 좌,우로 골고루 원소가 들어갈 조건을 만든다.
샘플을 보고 규칙성을 찾아보니 [...prev.., parent, ...next..] 리스트가 이렇게 있다면 parent을 제외하고 prev에 속한 원소들 중에서는 항상 위치상 중간값이 parent의 left 노드가 되고 next에 속한 원소 중 중간값이 parent의 right 노드가 된다. 원소의 길이의 중간값에 있는 원소가 부모노드가 된다는 것을 발견하고 길에 따라 left, right로 나눠서 재귀로 풀기로 했다.
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리스트 인덱승 list[:mid], list[mid+1:]를 이용해 left, right를 따로 구하지 않고 바로 매개변수로 넘겨 줄 수 있고
리스트 슬라이싱을 이용할때 인덱스가 만약 범위를 넘어가더라도
빈 리스트를 반환하기 때문에 에러처리에서도 용이하다.
앞으로 left, right등 이진 탐색을 할 때에는 리스트 슬라이싱을 꼭 머릿속에서 인출 하도록 해야겠다.
