Leetcode Python - 225. Invert Binary Tree

Leetcode #226 - Invert Binary Tree

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 226 ‘Invert Binary Tree’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 post-order로 traversal 하면서 left와 right을 바꾸어주는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        head = root
        stack = [root]
        
        while stack:
            node = stack.pop()
            
            if not node:
                continue
                
            tmp = node.left
            node.left = node.right
            node.right = tmp
            
            stack.append(node.left)
            stack.append(node.right)
        
        return head

시간복잡도는

• O(n) : 모든 노드 한번씩 방문

공간복잡도는

• O(1) : 상수