이진 트리 반전

이진 트리(T)를 고려하십시오. T의 반전은 또한 T의 왼쪽 및 오른쪽 자식이 교체된 이진 트리(M)입니다.



솔루션을 확인하기 전에 이 문제를 해결하고 싶은 경우. Leetcode에서 사용해보세요😉 .

https://github.com/Rage-ops/Leetcode-Solutions에서 다른 leetcode 문제에 대한 제 솔루션을 찾을 수 있습니다.

해결책

반복 및 재귀적으로 이 문제를 해결할 수 있습니다.

leetcode의 상용구 코드를 사용하여 두 가지 접근 방식을 모두 보여드리겠습니다. 알고리즘 작동 방식을 이해하면 솔루션을 직접 제출하고 확인할 수 있습니다.

재귀적 접근

원래 이진 트리를 가져 와서 반전된 이진 트리를 반환하는 반전 함수를 만들어 봅시다.

반전 함수의 기능은 다음과 같아야 합니다.

현재 노드의 왼쪽 및 오른쪽 자식 노드를 바꿉니다.

왼쪽 자식에 대해 invert를 호출합니다.

올바른 자식에 대해 반전을 호출합니다.

너무 쉽게 들리죠?. 네 😄입니다. 우리는 문자 그대로 이 세 줄의 코드로 이 문제를 재귀적으로 해결할 수 있습니다.

# 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:
        self.helper(root)
        return root

    # recursive     
    def helper(self, node):
        if node:
            node.left, node.right = node.right, node.left
            self.helper(node.left)
            self.helper(node.right)

반복적 접근

BFS를 사용하여 트리를 탐색하고 모든 노드의 왼쪽 및 오른쪽 자식을 바꿉니다.

# 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 queue import Queue
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        return self.iterative_invert(root)

    def iterative_invert(self, root):
        if root:
            q = Queue()
            q.put(root)
            while q.qsize() > 0:
                node = q.get()
                node.left, node.right = node.right, node.left
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
        return root

Time Complexity: O(N) as we are visiting each node at once.Space Complexity: O(N) since in the worst case, the queue will contain all nodes of the binary tree.
시간 및 공간 복잡성은 재귀 및 반복 접근 방식 모두에서 동일합니다. 재귀의 경우 최악의 경우 스택에 함수 호출n을 동시에 배치할 수 있습니다.