LeetCode 226(Invert Binary Tree, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• binary tree의 root가 주어졌을 때, 이를 invert한 root를 반환
• 예시) input이 [4,2,7,1,3,6,9] 이면 output이 [4,7,2,9,6,3,1]로 각 노드의 왼쪽과 오른쪽을 바꾼 root를 반환

3. 처음 풀이 

• 결국 재귀를 써서, root.right를 root.left에, root.left를 root.right에 두는 것을 반복 
  
  • TreeNode(root.val, self.invertTree(root.right), self.invertTree(root.left))
• 기본 로직으로 root가 None이면 root 반환

# 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 root is None:
            return root

        return TreeNode(root.val, self.invertTree(root.right), self.invertTree(root.left))

4. 다른 풀이

• 거의 대부분의 풀이가 위의 방식처럼 작성되어 있었다. 
• runtime 가장 빠른 코드로 보니, 거의 비슷하다. 아래풀이가 약간 다른 풀이
• 처음 풀이의 경우, 새로운 노드를 생성하고, 왼쪽 서브트리와 오른쪽 서브트리를 반전하는 형태로 짰다면,
• 아래는 주어진 노드의 왼쪽과 오른쪽 서브트리를 직접 교환하는 방식으로 작성이 되어있음.
• 아래의 코드가 추가적인 노드 생성 없이 직접 노드 값을 교환하므로 메모리 사용이 효율적 

# 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 None

        temp = root.left
        root.left = root.right
        root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root