[코딩 인터뷰 준비] 이진 트리 알고리즘 - Invert Binary Tree

코딩 면접을 준비하기 시작했을 때, 가장 자신 있었던 문제가 바로 이진 트리 반전이었습니다. 자료구조 수업에서 한 시간도 안 걸려 외운 단순한 재귀였거든요. 그런데 막상 모의 면접을 한 번 본 적이 있는데, 그 자리에서 제 머리가 하얘져 버렸습니다. 트리를 종이 위가 아니라 키보드 옆에 두고 풀려니까 평소엔 당연히 알던 참조 순서가 갑자기 헷갈리더라고요. 자식을 먼저 바꿔서 재귀를 호출하면 무한 루프에 빠지는 바람에 면접관이 살짝 미소 짓는 듯했고, 결국 저는 그 자리에서 시간 제한 안에 풀어내지 못했습니다. 그때부터 깨달았는데, 트리 문제는 알고리즘을 아는지가 아니라 참조 한 줄을 어디에 두고 어디서 끊느냐를 보는 문제였습니다.

실력이 출중한 분들도 같은 문제로 헤맨 사례가 있다는 일화를 훗날 접했을 때, 저는 오히려 마음이 놓였습니다. 제가 못 푼 게 알고리즘을 몰라서가 아니라 면접이라는 압박 환경에서 손이 굳었기 때문일 수도 있다는 생각이 들었기 때문입니다.

이 글에서는 제가 그때 실제로 부딪혔던 흔한 실수 세 가지와 그 해결 흐름을 먼저 정리해 보고, 간결한 자바 풀이와 복잡도 분석까지 함께 살펴보겠습니다.

제가 처음에 자주 했던 실수

저는 이 문제를 풀면서 같은 실수를 여러 번 반복했습니다. 그중에서도 특히 자주 했던 세 가지를 먼저 정리해 보면, 같은 시행착오를 피해 가시는 데 도움이 될 것입니다.

1. 재귀 호출 전에 자식 노드를 교체해서 이미 바뀐 subtree를 다시 처리하는 실수
2. 왼쪽 subtree 결과를 저장하지 않고 그대로 오른쪽에 덮어써서 왼쪽이 통째로 사라지는 실수
3. 재귀까지는 잘 호출했는데 끝에서 루트 노드를 반환하지 않아서 호출 측으로 null이 전달되는 실수

첫 번째 실수는 자식을 먼저 바꾼 뒤에 재귀를 호출하는 경우입니다. 이렇게 하면 이미 뒤집힌 subtree를 다시 한 번 더 뒤집게 되어 결과가 엉뚱하게 나옵니다. 두 번째 실수는 root.left에 invertTree(root.right) 결과를 넣은 다음, root.right에 곧바로 invertTree(root.left)를 호출해 버리는 흐름입니다. 이때 root.left는 이미 첫 줄에서 새로운 subtree를 가리키고 있기 때문에, 두 번째 호출은 엉뚱한 쪽을 또 뒤집게 됩니다. 세 번째 실수는 재귀와 교체를 잘 끝냈는데 마지막에 return root를 빠뜨리는 경우입니다. 호출 측에서는 null이 반환되어 트리가 통째로 사라진 것처럼 보이게 됩니다.

이런 시행착오를 겪고 나서 제가 익힌 패턴은 항상 같습니다. 먼저 왼쪽과 오른쪽 subtree의 반전 결과를 각각 임시 변수에 저장하고, 저장된 두 값을 서로 교환한 다음에 비로소 현재 노드를 반환하는 것입니다. 한 줄이라도 순서가 뒤틀리면 결과가 깨진다는 걸 반복해서 체득했습니다.

문제를 풀어보겠습니다.

그러면 이제 그 흐름 그대로 자바 코드로 옮겨보겠습니다. 입력으로 주어지는 클래스는 다음과 같습니다. 노드 하나당 값과 왼쪽·오른쪽 자식 참조를 갖는 흔한 정의이므로 한 번에 읽히실 것입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

푸는 방법은 크게 두 가지가 있습니다. 재귀로 풀거나 스택으로 풀거나 하시면 됩니다. 이번 글에서는 직관적이고 코드량도 적은 재귀 풀이를 먼저 살펴보겠습니다.

public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }

위 코드의 핵심은 첫 줄에서 왼쪽 자식을 임시 변수에 미리 저장해 두는 데 있습니다. 그다음에 root.left에는 오른쪽 subtree를 재귀로 뒤집은 결과를 넣고, root.right에는 아까 저장해 둔 원래 왼쪽 subtree를 뒤집은 결과를 넣습니다. 마지막에 현재 노드를 반환하면 호출 측은 바뀐 트리 전체를 이어 받을 수 있습니다.

시간 복잡도는 모든 노드를 한 번씩 방문해야 하므로 O(N)이고, 공간 복잡도는 재귀 호출 스택 깊이에 비례하므로 최악의 경우 O(N)입니다(N은 노드의 개수).

위에서 정리해 드린 것처럼, 이 문제는 이름만 들으면 어려워 보이지만 실제로는 임시 변수 하나만 잘 다루면 되는 꽤 깔끔한 문제입니다. 막히는 분은 위에서 말씀드린 세 가지 흔한 실수를 의식하면서 한 번 더 풀어보시면 분명 통과하실 수 있을 것입니다. 재귀가 익숙해지셨다면 이어서 스택 풀이도 직접 한 번 구현해 보시길 권해 드립니다. 같은 패턴을 자료구조 하나로 옮기는 연습이 되어 큰 도움이 됩니다.