[1스4코2파] # 163. LeetCode Pattern 226. Invert Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (163차)
[4코1파] 2023.01.13~ (155일차)
[1스4코1파] 2023.04.12~ (66일차)
[1스4코2파] 2023.05.03 ~ (45일차)

Today :

2023.06.14 [163일차]
LeetCode Patterns
226. Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree/description/

226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/description/

문제 설명

binary tree가 주어졌을 때 left node와 right node를 swap 하는 것임

문제 풀이 방법

이것 또한 recursion으로 풀면되는데
여기서 처음에.. 말단 leaf 까지 가는 것 때문에 중간에 끊느라 힘들었음

• base로 root가 none 이면 root return
• left 값을 변수에 넣고 node.right 와 node.left를 swap 해줌 ㄱ~!

내 코드

(1) recursion 1

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(val=4, left=TreeNode(2, left=TreeNode(1),right=TreeNode(3)),
               right=TreeNode(7, left=TreeNode(6), right=TreeNode(9)))


class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

(2) recusion 2

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: TreeNode) -> TreeNode:
        if not root:
            return root
        leftval = root.left
        root.left = self.invertTree(root.right)
        root.right = self.inverTree(leftval)
        
        return root

증빙

이거 recursion 1

이거 recursion 2

여담

트리지옥 언제 트리천국됨?

• bfs로 왜 안푸냐고 양재호가 모라고 해서 bfs로도 푼거 배껴서 올림.. 외우면 내꺼

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                node.left, node.right = node.right, node.left
                queue.append(node.left)
                queue.append(node.right)

        return root