[99클럽 코테스터디 2기][Python/비기너] 14번째 문제: Invert Binary Tree

오늘의 주제도 dfs/bfs

[Invert 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        else:
            root.left, root.right =self.invertTree(root.right), self.invertTree(root.left)
            return root

알고리즘
먼저, 꼭 지정해줘야하는 노드가 없을때 return 조건 먼저 지정해준다.
노드가 있다면 왼쪽 노드와 오른쪽 노드를 바꿔주는 swap해주는 코드를 추가해준다.
이때, 순환하면서 swap해줄 수 있도록 왼쪽노드와 오른쪽 노드를 재귀함수로 호출해준다.

회고
이번에도 요 며칠간 했던 코드를 토대로 일단 작성해보았다.
오늘 문제는 중간에 521에러가 나서 정신없이 하느라 그 전 코드를 캡쳐해두지 못했다 ㅜㅜ
그러나 그전 코드도 지금 코드와 크게 다르지 않았는데, 기억을 더듬어 적어보자면

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        else:
        	temp=root.left
        	root.left=root.right
            root.right
            

정확하진 않지만, temp라는 빈노드를 만들어서 변수 변환할때 처럼 구성했었던 것 같다.
그러나 예상했듯이 오류가 발생했고,당연히 순환하는 부분이 없으니 전체를 돌고 있지도 않았다.
노드를 담는게 어렵다면 아예 그 자체끼리 바꿔주면 되지않을까 싶어 어딘가에서 봤던 swap방식을 사용했다.
어제 풀었던 문제에서 재귀함수자체를 or , and 연산해줬던 것처럼 여기서도 재귀함수를 호출해서 swap해주면 전체를 순회하면서 값을 받을 수 있지않을까? 하여 어제 알게된 알고리즘을 사용했다.

결과는..!! 너무 빠르게 성공해서 오히려 당황했다..
확실히 dfs 문제는 패턴이 있는 느낌..?
이번 중간고사가 끝나면 dfs 문제의 난이도를 높여서 완전 정복해봐야겠다...!!!!!

그리구 절대 까먹으면 안되는!! node가 없을때 return해주는 조건 지정!!