오늘의 주제도 dfs/bfs
[Evaluate Boolean Binary Tree]
문제
입력과 출력
코드
# 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 evaluateTree(self, root: Optional[TreeNode]) -> bool:
if root.val<=1:
return root.val
if root.val==2:
return self.evaluateTree(root.left) or self.evaluateTree(root.right)
else:
return self.evaluateTree(root.left) and self.evaluateTree(root.right)알고리즘
#0과1은 true와 false인 boolean 형태
#2일때는 or 연산, 3일때는 and 연산
먼저, root의 값이 0이나 1일 때는 값을 반환해준다.
값이 2일 때는 self 재귀함수를 호출하여 왼쪽과 오른쪽 노드의 or 연산을 해준다. 3일때는 and 연산
회고
먼저, 처음에 써내려간 코드이다.
뭔가 어제 이틀간 익힌 dfs 알고리즘을 써보려했으나 실패~하였다.
그러나 case2가 accepted 된걸 보니 첫값은 잘 받고 트리를 못돌고 있구나! 라는 사실을 짐작할 수 있었다.
근데 대체 뭐하는건지,, 0이거나 1이거나를 해야하는데 조건을 ㅋㅋㅋㅋ 잘못달아놨었다.. 이건 나중에 수정했는데 그 부분을 캡쳐해둔게 없어서 이것으로 대체한다..!
일단 이쯤에서 알고리즘에 감을 잡았다. 위와 같이 왼쪽노드와 오른쪽 노드를 or 혹은 and 연산을 한값을 return 하면 되겠구나 싶었다.
이 다음에는 dfs재귀함수를 호출하려 했지만, 그것보다는 evaluateTree자체를 호출하면 된다는 생각이 들어서 수정하였고,
오류가 났다..
class Solution:
def evaluateTree(self, root: Optional[TreeNode]) -> bool:
if root.val<=1:
return root.val
if root.val==2:
return evaluateTree(root.left) or evaluateTree(root.right)
else:
return evaluateTree(root.left) and evaluateTree(root.right)캡쳐를 해놓지 않아 오전에 풀었던 기억을 더듬어 써보았다
이런식으로 짰었는데, 정답코드와의 차이점이 보이나..?!
self에 대한 개념이 없어서 그냥 바로 evaluateTree를 호출했고, 결과는 당연히 오류가 났다.
self의 존재를 알고 수정해서 accepted된 코드가 위에 적어둔 정답 코드 ㅎ
self
- 클래스 내에 정의된 함수 : 메서드
- 메서드의 첫번째 인자는 항상 self여야함
- 해당 매개변수가 해당 객체의 정보라는 것을 표시하기 위해서는 매개변수의 값을 객체에 바인딩, 매핑시켜줘야함
- 객체마다 고유한 메모리 영역 보유
-> 결론은 self객체를 가지고 있는 함수는 self로 호출해줘야 정확히 값을 받아온다는 것 같다.
