99클럽 코테 스터디 11일차 TIL : 깊이/너비 우선 탐색 (DFS/BFS)+후위순회(트리순회)

 

https://leetcode.com/problems/evaluate-boolean-binary-tree

 

이번 문제도 어제처럼 노드 무더기로 나오는 문제

머리아프지만 뭔가 익숙해지는건가

재밌다

 

 

오늘 추가로 배운 개념은 후위순회

https://yoongrammer.tistory.com/70

[자료구조] 트리 순회 (Tree Traversal)

 

스터디원이 올려주신 자료인데 이해하기가 쉽게 정리되어있음

문제풀기전에 노드 그림 한번보고

이거 한번 봤더니 대충 어떻게 풀어야될지 감이와서

바로 문제 풀기

 

# 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 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:
            #왼쪽 비교: 왼쪽에 자식 노트있는지 없는지 확인
            if root.left is None and root.right is None:
                #루트기준으로 양 옆으로 없음-> 그대로 반환
                return bool(root.val)
            root_left = self.evaluateTree(root.left) #정의되지않았대서 self(재귀호출)
            root_right = self.evaluateTree(root.right)
            if root.val == 2: # or은 2 값이라함(문재)
                return root_left or root_right
            if root.val == 3: # and는 3
                return root_left and root_right

 

자세히 리뷰해보자면

# 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 TreeNode:
    def __init__(self,val=0, left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

 

먼저 친절한 리트코드의 힌트로

클래스 TreeNode 초기 코드를 만들어주고

 

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        #뭔가 자꾸 밑에서 삭제되는거보니 후위 순회인듯?(삭제할떄주로사용)
        #자식이없는 노드를 리프노드라고함
        if root:

 

밑에 해결할 클래스(solution)도 선언해주고

if root: 로 루드노드가 있을때만 실행되도록 해줬다

아 ...

그럼 루트노드없이 아무것도 없을때는

none리턴하게 밑에 써줘야하나?

아무튼 루트가 있다는 가정하에

 

            #왼쪽 비교: 왼쪽에 자식 노트있는지 없는지 확인
            if root.left is None and root.right is None:
                #루트기준으로 양 옆으로 없음-> 그대로 반환
                return bool(root.val)

 

이 루트노드가 리프? 인지 아닌지 판단해야댐

-> 리프면 T/F 라고했으니

바로리턴하게

 

## 처음 알게된거: 리프 - 밑에 자식노드가 없는 애

 

아무튼 왼쪽이랑 오른쪽이 없으면(none)

root의 val 값을 bool로 체크해서 리턴함

=> 왜 bool 체크하냐 ? 그냥 리턴하면 1.0나오니까

bool함수로 T/F 변환해서 리턴

 

            root_left = self.evaluateTree(root.left) #정의되지않았대서 self(재귀호출)
            root_right = self.evaluateTree(root.right)
            if root.val == 2: # or은 2 값이라함(문재)
                return root_left or root_right
            if root.val == 3: # and는 3
                return root_left and root_right

 

그리고 마지막으로

루트값이 2 냐 3이냐 에따라

or, and 값으로 리턴하면 끝