[Java] 트리, 재귀 | LeetCode 226 Invert Binary Tree (귀납적으로 생각하기)

문제 링크

https://leetcode.com/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 입출력

• 입력: 이진 트리의 루트(root) 노드
• 출력: 각 노드의 자식 좌우를 뒤바꾼 이진 트리의 루트 노드

모든 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환하면 되는 문제다.

 

단순하게 모든 노드를 순회하면서 해당 노드의 자식들을 swap하면 되는데, 문제를 푸는 과정에서 재귀적으로 계속 swap해주면 되겠다는 것은 알았지만 재귀 호출 순서를 깊게 상상하면서 구현하는데 삽질을 해서 느낀 바를 정리해보려고 한다.

 

예시 

    4
   /   \
  2     7
 / \     / \
1   3 6   9

 

재귀 호출 순서 (깊이 우선 탐색)

1. invertTree(4) 호출

현재: 4
left = 2, right = 7
교환 후: 4의 left←7, right←2

 

2. invertTree(7) 호출 (4의 새로운 left)

현재: 7
left = 6, right = 9
교환 후: 7의 left←9, right←6

 

3. invertTree(9) 호출 (7의 새로운 left)

현재: 9
left = null, right = null
변화 없이 반환

 

4. invertTree(6) 호출 (7의 새로운 right)

현재: 6
left = null, right = null
변화 없이 반환

 

5. invertTree(2) 호출 (4의 새로운 right)

현재: 2
left = 1, right = 3
교환 후: 2의 left←3, right←1

 

6. invertTree(3) 호출 (2의 새로운 left)

현재: 3
left = null, right = null
변화 없이 반환

 

7. invertTree(1) 호출 (2의 새로운 right)

현재: 1
left = null, right = null
변화 없이 반환

 

최종 결과

    4
   /   \
  7     2
 / \      / \
9   6 3   1

 

 

위의 과정처럼 재귀적으로 호출되는 것은 맞다.

하지만 재귀 문제를 풀 때마다 이렇게 모든 호출 과정을 떠올리는 것이 오히려 생각을 복잡하게 만들고 있었다.

 

정답 코드를 보자.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    // 1. 임시 변수에 저장
    TreeNode temp = root.left;

    // 2. 교환
    root.left = root.right;
    root.right = temp;

    // 3. 자식 노드들도 같은 작업 수행
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

 

위 문제의 핵심은 "각 노드에서 왼쪽과 오른쪽 자식을 교환하기"이다.

 

invertTree(TreeNode root)가 지금 당장 할 일은 root 노드의 왼쪽, 오른쪽 자식만 바꾸는게 전부다.

 

root 노드의 자식들을 swap한 뒤, 

 

invertTree(왼쪽 자식 노드), invertTree(오른쪽 자식 노드)을 호출하면,

부모가 했던 일(왼쪽과 오른쪽 자식을 교환하기)을 동일하게 수행하게 하는 것이다.

 

invertTree(현재 노드) 메서드 입장에서 생각해보면,

• "내 할 일은 현재 노드의 왼쪽과 오른쪽 자식을 교환하는 것뿐이다."
• 내 일만 마친 뒤, invertTree(왼쪽 자식 노드), invertTree(오른쪽 자식 노드)을 호출해 자식들에게 같은 일을 시키자.
• "자식 노드들도 각자 알아서 같은 작업을 할 것이다" => 이 과정을 너무 깊게 생각하지 말자.

 

 

따라서 재귀적으로 문제를 풀 때는, 종료조건(base-condition)과 핵심 로직(해당 문제에서는 자식 교환 과정)만 정확하게 구현하고

올바르게 다음 일할 주체만 정확히 골라줬다면,

이어서 호출된 주체가 그들의 역할을 동일하게 잘 수행할 것이라고 믿자.

 

 

도미노도 첫번째 도미노만 밀면 모든 도미노가 넘어질 것이라고 당연하게 믿는 것과 동일하다.

즉, 우리는 밀기만 하면 된다.

 

 

 

바킹독 알고리즘 강의에서 귀납적으로 사고하라 했던 것과 같은 맥락인 것 같아, 혹시 재귀 문제에 어려움을 느낀다면 아래 강의를 들어보는 것을 추천한다.

 

 

https://youtu.be/8vDDJm5EewM?si=H2hO9hU-jxs-5tu9