오늘의 주제는 '이진트리'
[Range Sum of BST]
문제
입력과 출력
코드
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
def bstSum(node):
if not node:
return 0
if node.val>=low and node.val<=high:
return node.val+bstSum(node.left)+bstSum(node.right)
elif node.val<low:
return bstSum(node.right) #노드로 바로 가는게 아니라 재귀함수.. 호출해서 다시 탐색하게
elif node.val>high:
return bstSum(node.left)
return bstSum(root)알고리즘
재귀함수로 구현하지 않으면 계속 오류가 나고, 구현 중간에 문제가 생겨 재귀함수로 구현해주었다.
bstSum 함수를 선언하여 입력값은 node로 설정해놓고,
노드가 없을 때 조건을 선언해준다.
그리고 노드의 값이 low값보다 크거나 같고 high값보다 작거나 같으면
node의 값과 노드의 왼쪽, 오른쪽에서의 함수를 더하는 값을 return한다.
노드의 값이 low보다 작으면 node.right
노드의 값이 high보다 크면 node.left
회고
이진트리를 공부만 해봤지 코드로는 처음 구현해본 나..! 험난했다
그치만 구현하다 보니 정처기에서 많이,, 아주 많이 본 형태가 되어가서 배웠던 부분을 써먹을 수 있었다 ㅎ
처음에는 이런식으로 코드를 구성했었다.. 그러나 트리노드 형식으로 선언되어 있어 배열처럼 사용할 수가 없었고,,
그 다음으로 구성했던 코드는 이렇게
주석 달린 걸 보면 알겠지만 ,,, 저 부분이 도저히 의문이 풀리지 않다가
정처기에서 봤던 이진트리 코드가 생각났다..!
return node.val+bstSum(node.left)+bstSum(node.right)
이 부분을 수정하고 보니 다른 if문에서도 node.right라고만 선언해놓은 것을 발견하고
어라? 이러면 아무것도 안되는데 왜 이렇게 선언했더라,, 하면서 재귀함수를 호출하는 식으로 수정하였다
드디어 성공... ㅜㅜ
- 재귀함수
- 이진트리 탐색법 : 새로운 알고리즘을 공부해서 , 이 부분에 대해 좀 더 다양한 풀이를 찾아보려 한다.
- 이진트리라서 그런지 그림을 그리면서 코드를 수정하니 훨씬 수월했다 ㅎ..
- 이진트리를 기반으로 너비 우선 탐색법과 깊이 우선 탐색법 알고리즘도 공부해보려한다.
풀이세션
클럽장님 피드백
->이진트리는 그 자체로 왼쪽에 작은값, 오른쪽에 큰값이 있는 것이라서 굳이 완전탐색할 필요가 없다.
노드 값이 없을때 left right 다 탐색하는 거보단 조건문 한줄로 return만 시켜준다면 좀더 좋을 것이다.
챌린저분들의 문제와 코드를 보면서 ,, 나는 아직도 멀었구나 더 열심히해야지를 다시 한번더 느끼며,, 오늘 TIL 마무리한다...
