[Leetcode] 226. Invert Binary Tree

問題のショートカット
DFS + recursion
Time Complexity: O(n)O(n)O(n)
空間複雑度:O(h)≒O(n)O(h)近似O(n)O(h)≒O(n)h:木の高さ

# 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)O(n)O(n)
Space Complexity: O(n)O(n)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