Symmetric Tree (Recursive)

LeetCode의 Binary Tree 튜토리얼의 두 번째 섹션의 두 번째 문제인 Symmetric Tree다.

Explore - LeetCode

주어진 트리가 대칭 구조인지 판별하는 문제로 대칭 구조인 트리라는 것은 다음과 같은 트리를 의미한다.

마치 거울을 보는 것처럼 좌우반전을 해도 그 모양과 노드의 값이 동일한 트리를 대칭 트리라고 한다.

위처럼 대칭이 아닌 트리는 대칭 트리가 아니다. 이를 구분하여 대칭 트리 여부를 반환하는 것이 문제의 요구사항이다. 그럼 이를 어떻게 해결할 수 있을까?

 

처음에 생각했던 방법은 큐나 스택 같은 자료구조를 이용하는 것이었다. 대칭이기 때문에 한쪽에는 큐로, 한쪽에는 스택으로 노드를 삽입해서 둘 다 하나씩 꺼내면서 비교하면 되지 않을까? 싶었지만 이번 섹션이 문제를 재귀적으로 풀어보는 걸 연습하는 것이기 때문에 이를 사용하지 않는 해결방법을 생각해보았지만 잘 떠오르지 않았다. 그래서 풀이를 참고한 결과 서브 트리를 재귀 호출하는 방식으로 풀 수 있었다.

 

이번 풀이에서 생각하지 못했던 점은 재귀 함수에 두 개 이상의 노드를 전달하는 방법이었다. 지금까지 DFS나 BFS 문제를 풀 때는 한 번에 하나의 노드만 재귀 함수에 전달했기 때문에 이번 문제처럼 두 개의 노드를 전달해보려는 생각은 못했기 때문에 좀 까다로웠던 것 같다. 풀이에서 설명한 알고리즘을 그림으로 나타내 보면 다음과 같다.

핵심적인 원리는 대칭 트리의 경우 왼쪽 자식 노드, 오른쪽 자식 노드가 각각 현재 트리의 서브 트리라는 것이다. 각 노드의 높이를 레벨로 표현할 때 레벨 1은 루트 노드기 때문에 무조건 대칭이며 확인할 필요가 없다. 레벨 2는 루트 노드의 왼쪽, 오른쪽 자식 노드기 때문에 그냥 두 자식 노드의 존재 유무와 값만 비교해서 대칭 여부를 확인할 수 있다.

까다로운 건 레벨 3부터인데 여기서부터 대칭 트리가 되려면 왼쪽 레벨 2 노드의 왼쪽 자식 노드가 오른쪽 레벨 2의 오른쪽 자식 노드와 일치해야 한다. 마찬가지로 오른쪽 자식 노드는 왼쪽 자식 노드와 일치해야 한다. 레벨 4까지 가면 자식 노드가 훨씬 많아지기 때문에 일일이 확인하기 까다로운데 이를 어떻게 해결할 수 있을까? 이는 위에서 언급했듯이 전체 트리를 한 번에 비교하지 않고 서브 트리로 나눠서 비교하는 것이다.

만약 레벨 4까지 대칭 트리를 구축한다면 위와 같은 모습이 될 것이다. 이를 서브 트리로 분리하면 다음처럼 분리할 수 있다.

뭔가 규칙이 보이는가? 더 깊게 내려가지 않고 레벨 2의 관점에서 보면 왼쪽 레벨 2 노드의 왼쪽 서브 트리(파란색 박스)는 오른쪽 레벨 2 노드의 오른쪽 서브 트리(파란색 박스)와 대칭이어야 한다. 그리고 레벨 2의 왼쪽 노드의 오른쪽 서브 트리(빨간색 박스)는 레벨 2의 오른쪽 노드의 왼쪽 서브 트리(빨간색 박스)와 대칭이어야 한다. 여기서 두 서브 트리가 대칭이 되기 위한 조건은 위의 레벨 1 때 봤듯이 다음과 같다.

• 왼쪽 서브 트리의 왼쪽 노드는 오른쪽 서브 트리의 오른쪽 노드와 동일하다.

• 왼쪽 서브 트리의 오른쪽 노드는 오른쪽 서브 트리의 왼쪽 노드와 동일하다.

문제에서 요구하는 대칭 트리는 자식이 두 개인 이진트리기 때문에 레벨이 아무리 증가해도 이와 동일한 로직으로 노드 대신 서브 트리를 전달해서 재귀적으로 대칭 여부를 판단할 수 있다. 그렇기 때문에 레벨 2 노드의 각 서브 트리를 두 쌍으로 묶어서 대칭을 비교하는 재귀 함수에 전달하여 호출하면 된다.

 

정리하면 다음과 같다.

• 레벨 N(N>1)의 대칭 노드(노드 N1, N2)가 있다.

• 레벨 N의 왼쪽 노드(N1)의 왼쪽 서브 트리(N1-1)는 오른쪽 노드(N2)의 오른쪽 서브 트리(N2-2)와 대칭이어야 한다.

• 레벨 N의 왼쪽 노드(N1)의 오른쪽 서브 트리(N1-2)는 오른쪽 노드(N2)의 왼쪽 서브 트리(N2-1)와 대칭이어야 한다.

• 이 과정을 재귀적으로 N+1 레벨에서 N1-1과 N2-2 그리고 N1-2와 N2-1 끼리 반영한다.

• 즉 N+1 레벨에서 두 대칭 노드는 N 레벨의 N1, N2 노드의 서브 트리가 된다.

그럼 레벨이 증가할수록 대칭으로 비교해야 하는 쌍이 늘어날 텐데 이를 직접 관리해줘야 할까? 그럴 필요 없이 재귀 호출을 통해 자기들이 알아서 서브 트리끼리 비교하기 때문에 호출시켜주기만 하면 된다. 대신 코드에서는 현재 노드의 자식 노드가 존재하지 않을 때 탐색을 종료하도록 구현만 해주면 된다. 이를 기반으로 구현한 코드는 다음과 같다.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        if((root.left != null && root.right == null) ||
          (root.right != null && root.left == null)) return false;
        
        return checkSymmetric(root.left, root.right);
    }
    
    private boolean checkSymmetric(TreeNode leftNode, TreeNode rightNode){
        if(leftNode == null && rightNode == null) return true;
        if(leftNode == null || rightNode == null) return false;
        if(leftNode.val != rightNode.val) return false;
        
        return checkSymmetric(leftNode.left, rightNode.right) &&
            checkSymmetric(leftNode.right, rightNode.left);
    }
        
}

먼저 직접 재귀 함수를 호출하기 전에 루트 노드 하나만 있거나 루트 노드의 자식 노드가 대칭이 아닌 경우 미리 반환해준다. 그리고 재귀 함수를 호출하는데 이때 루트 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 전달하면서 탐색을 시작한다.

재귀 함수 내부에서는 매개변수로 받은 왼쪽 서브 트리와 오른쪽 서브 트리가 둘 다 null인 경우 대칭이라고 판단한다. 이는 위의 그림과 같은 경우를 상정한 것이다. 왼쪽 레벨 2 노드의 오른쪽 서브 트리가 leftNode로, 오른쪽 레벨 2 노드의 왼쪽 서브 트리가 rightNode로 전달됐다고 생각하면 된다. 둘 중 하나만 null이라면 대칭이 안 맞기 때문에 아니라고 판단한다.

 

레벨이 증가할수록 하위 단계의 서브 트리는 멀어지는데 그 사이의 간격을 넘어서 볼 수 있는 걸까? 이는 재귀 함수의 매개변수로 양쪽 서브 트리가 전달되기 때문에 거기서 왼쪽, 오른쪽 자식 노드만 참조하면서 진행하면 가능한 것이다.

 

 

나도 풀이를 보고 알 수 있었던 만큼 생각해내기는 어렵지만 구상만 할 수 있다면 간단하고 효율적인 풀이 방법이었다.