[Invert Binary Tree]

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

 

Given the root of a binary tree, invert the tree, and return its root.

 

이진트리가 나오고 트리를 좌우 바꾸기

 

ⓐ재귀적 방법: 이걸로 풀었는게 이게 재귀적 방법인건 gpt가 알려줘서야 알았다.

 

수도코드

 

function invertTree(root):
    if root is null:
        return null
    
    // 왼쪽과 오른쪽 자식을 임시 변수에 저장
    temp = root.left
    
    // 왼쪽과 오른쪽 자식을 교환
    root.left = invertTree(root.right)
    root.right = invertTree(temp)
    
    return root

 

ⓑ반복적 풀이( BFS/ DFS) 풀기

 

ⓑ-1 BFS로 풀기

큐사용하기

큐가 빌때까지 반복 큐에서 노드를 하나 꺼내서 노드의 왼쪽과 오른쪽 자식을 교환

쪽 자식있으면 큐에 추가한다

 

수도코드

function invertTree(root):
    if root is null:
        return null
    
    queue = new Queue()
    queue.add(root)
    
    while queue is not empty:
        current = queue.poll()
        
        // 현재 노드의 왼쪽과 오른쪽 자식을 교환
        temp = current.left
        current.left = current.right
        current.right = temp
        
        // 왼쪽 자식이 있으면 큐에 추가
        if current.left is not null:
            queue.add(current.left)
        
        // 오른쪽 자식이 있으면 큐에 추가
        if current.right is not null:
            queue.add(current.right)
    
    return root

 

문제상황 

push pop 쓰는 줄알았는데 스택에서 쓰는 거라고함

 

 

해결: 

 

큐에서 offer를 사용하는 이유

용량이 제한된 queue에서는 offer 사용함(요소를 큐에 추가하며 성공하면 true, 실패하면 faluse를 반환한다)

poll() peek() 메서드 사용 권장 

add 사용은 일반적인 큐 구현에서만 사용한다.

 

ⓑ-2 DFS 스택을 사용

깊이 우선 처리 스택이 빌때까지 반복한다.

스택에서 노드를 꺼내서 왼쪽과 오른쪽 자식을 교환한다.

 

수도코드

function invertTree(root):
    if root is null:
        return null
    
    stack = new Stack()
    stack.push(root)
    
    while stack is not empty:
        current = stack.pop()
        
        // 현재 노드의 왼쪽과 오른쪽 자식을 교환
        temp = current.left
        current.left = current.right
        current.right = temp
        
        // 오른쪽 자식이 있으면 스택에 추가 (LIFO 특성 때문에 오른쪽 먼저)
        if current.right is not null:
            stack.push(current.right)
        
        // 왼쪽 자식이 있으면 스택에 추가
        if current.left is not null:
            stack.push(current.left)
    
    return root