C#에서 재귀(Recursion)를 활용해 트리가 대칭인지 확인하는 방법

트리가 대칭(symmetric)이라는 것은 트리가 자기 자신의 거울상(mirror image)과 동일한 구조를 가진다는 의미입니다. 재귀적 접근 방식을 사용하면 이러한 대칭 여부를 효율적으로 판별할 수 있습니다.

재귀 방식의 기본 원리

재귀를 이용해 트리의 대칭 여부를 확인하는 과정은 다음과 같습니다.

먼저 트리가 null인지 검사합니다. 트리가 null이면 대칭으로 간주하고 true를 반환합니다.
트리가 null이 아니라면 isSymmetricMirror 메서드를 호출합니다.

isSymmetricMirror 메서드의 동작 방식

isSymmetricMirror 메서드에서는 왼쪽 자식 노드와 오른쪽 자식 노드의 값을 비교합니다.

왼쪽 자식과 오른쪽 자식이 모두 null이면 대칭으로 판단합니다.
둘 중 하나라도 null이면 비대칭으로 판단합니다.
두 노드의 값이 서로 다르면 비대칭으로 판단합니다.
위 조건에 해당하지 않으면, 왼쪽·오른쪽 자식을 교차하여 전달하면서 isSymmetricMirror를 재귀적으로 호출해 하위 레벨까지 계속 검사합니다.

예제 코드

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public bool isSymmetricRecursive(Node node)
    {
        if (node == null){
            return true;
        }
        return isSymmetricMirror(node.LeftChild, node.RightChild);
    }
    private bool isSymmetricMirror(Node node1, Node node2){
        if (node1 == null && node2 == null){
            return true;
        }
        if (node1 == null || node2 == null){
            return false;
        }
        if (node1.Value != node2.Value){
            return false;
        }
        return isSymmetricMirror(node1.LeftChild, node2.RightChild) && isSymmetricMirror(node2.LeftChild, node1.RightChild);
    }
}

실행 결과

아래와 같은 트리 구조에서 위 코드를 실행하면 대칭 여부가 출력됩니다.

결과로 True가 출력되었으므로, 해당 트리는 좌우가 대칭임을 확인할 수 있습니다. 핵심은 두 하위 트리를 교차(cross-compare)하며 재귀적으로 비교하는 부분으로, 이를 통해 트리 전체가 거울상 관계인지 정확히 판별할 수 있습니다.