[LeetCode] 226번: Invert Binary Tree

Hint

1. DFS 알고리즘 사용해야함
2. 왼쪽과 오른쪽에 자식 노드가 있다면 바꿔치기 해주면 됨

DFS 순서도

 

LeetCode 226번: Invert Binary Tree (풀어보기)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root):
        	# 노드인지 확인. 노드가 아니라면 None 값이기 때문에 not을 해줘야 True가 됨
            if not root:
                return root	# 노드가 아니기 때문에 바꿔치기 안하고 그냥 반환
            
            dfs(root.left)	# 왼쪽 노드의 자식 노드 뒤집기
            dfs(root.right)	# 오른쪽 노드의 자식 노드 뒤집기
            
            # 왼쪽 노드와 오른쪽 노드 바꿔치기
            root.left, root.right = root.right, root.left
            
            # 왼쪽 오른쪽 자식노드들을 바꿔치기 완료한 부모노드 반환하기
            return root	
        
        # 최종 노드 바꿔치기 된 트리 반환하기
        return dfs(root)