[python3] 226. Invert Binary Tree

풀이 일자: 23.02.18

난이도: [Easy]

분류: [Tree, DFS, BFS, Binary Tree]

문제 내용

이진트리의 root가 주어졌을 때 tree의 모든 노드의 좌우 위치를 바꾸는 게 문제의 내용이다.

 

 

문제 해결 흐름

1. 노드 순회가 필요하고 노드 순회 과정에서 단순히 자식 노드의 위치를 바꾸면 된다.

→ 일단 재귀적으로 구현해보자.

 

# 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]:
    
        def traverse(node: Optional[TreeNode]):
            if node is None:
                return;
            
            node.left, node.right = node.right, node.left;

            if node.left:
                traverse(node.left);
            if node.right:
                traverse(node.right);
        
        node = root;
        traverse(node);
        ans = root;
        return ans;

=> 함수를 재귀적으로 호출하게 되면 보통 런타임에서 호출시간 만큼의 손해를 보고 있다.

 

Time Complexity: O(N)

모든 노드를 순회해야 하기 때문에 N의 시간복잡도를 가지게 된다.

 

Space Complexity: O(H)

함수를 재귀적으로 사용하고 있기에 Tree의 높이 만큼의 stack call이 필요하다.

 

 

다른 해결 방식

1. 이번에는 While문으로 iterative하게 처리해보자.

→ 트리 순회를 while문으로 구성하기 위해 사용하는 자료구조인 queue를 이용하면 된다.

 

# 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]:
    
        q = deque();
        q.appendleft(root);

        while(len(q) != 0):
            node = q.pop();

            if node is None:
                continue;

            node.left, node.right = node.right, node.left;
            if node.left:
                q.appendleft(node.left);
            if node.right:
                q.appendleft(node.right);

        return root;

=> 반복문으로 하는 만큼 런타임 시간이 줄었지만 queue를 사용해야 하기 때문에 메모리 사용량은 늘었다.

 

Time Complexity: O(N)

모든 노드를 순회해야 하기 때문에 N의 시간복잡도를 가지게 된다.

 

Space Complexity: O(2^H)

이진트리의 최대 depth에 존재하는 node만큼의 공간복잡도를 가지게 될 것이다.

 

 

2. 런타임 시간도 짧고 메모리도 적게 사용하는 방법을 소개해본다면.. 

# 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):
        if root:
            invert = self.invertTree
            root.left, root.right = invert(root.right), invert(root.left)
            return root

https://leetcode.com/problems/invert-binary-tree/solutions/62714/3-4-lines-python/?orderBy=most_votes 

3-4 lines Python - Invert Binary Tree - LeetCode

 

 

문제 링크

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

Invert Binary Tree - LeetCode