[Leetcode] 226. Invert Binary Tree

문제 바로가기

DFS + recursion

Time Complexity: $O(n)$
Space Complexity: $O(h) \approx O(n)$ h: tree의 높이

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

BFS + iterative

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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
from collections import deque

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        q = deque()
        q.append(root)
        while q:
            front = q.popleft()
            if front is None:
                continue
            q.append(front.left)
            q.append(front.right)
            front.left, front.right = front.right, front.left
        return root