[Algorithm][LeetCode 101] Symmetric Tree

대칭 트리 (Symmetric Tree)

LeetCode 문제 중 하나인 Symmetric Tree는 이진 트리가 자기 자신을 기준으로 대칭인지 확인하는 문제입니다.

문제 설명

주어진 이진 트리의 루트 노드가 있을 때, 이 트리가 대칭 구조인지 확인하세요. 즉, 트리가 자기 자신을 중심으로 좌우가 거울처럼 대칭되어 있어야 합니다.

예시 1

Input: root = [1,2,2,3,4,4,3]
Output: true

예시 2

Input: root = [1,2,2,null,3,null,3]
Output: false

문제 조건

• 노드의 수: 1 이상 1000 이하
• 노드의 값: 1 이상 100 이하

1. 재귀(DFS)를 이용한 풀이

어제 풀었던 "같은 트리인지 확인하는 문제"의 접근을 응용하여, DFS로 공간 복잡도를 최소화하는 방법을 사용했습니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    let left = root.left;
    let right = root.right;
    const traverse = (left, right) => {
        // 두 값이 null일 때만 true를 반환
        if (!left && !right) return true;
        // 두 값 중 하나만 null이면 false
        if (!left || !right) return false;
        // 값이 다르면 false
        if (left.val !== right.val) return false;
        // 대칭 구조 비교를 위해 서로 반대 방향의 자식을 비교
        return traverse(left.right, right.left) && traverse(left.left, right.right);
    }
    return traverse(left, right);
};

• 장점: 공간 복잡도 최소화, 코드 이해 쉬움
• 단점: 트리의 깊이가 깊을 경우 call stack 초과 가능

2. 큐(BFS)를 활용한 반복적 풀이

재귀 대신 큐를 활용하여 반복적으로 비교하는 방식입니다. 대형 트리에서도 안정적으로 동작합니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) return true;
    const queue = [root.left, root.right];
    
    while (queue.length) {
        const left = queue.shift();
        const right = queue.shift();
        
        // 둘 다 null이면 대칭
        if (!left && !right) continue;
        // 하나만 null이면 대칭 아님
        if (!left || !right) return false;
        // 값이 다르면 대칭 아님
        if (left.val !== right.val) return false;
        
        // 대칭 비교를 위해 반대 방향 자식 추가
        queue.push(left.left);
        queue.push(right.right);
        queue.push(left.right);
        queue.push(right.left);
    }
    
    return true;
};

• 장점: call stack 초과 위험 없음, 대형 트리에서도 안정적
• 단점: 구현이 상대적으로 복잡

결론

두 방식 모두 대칭 트리를 검증하는 데에 적합하지만, 상황에 따라 선택이 달라질 수 있습니다. 트리의 깊이가 얕거나 재귀 방식에 익숙하다면 DFS를, 트리의 크기가 크거나 안정성을 중시한다면 반복적 BFS 방식을 추천합니다.