[LeetCode] 101. Symmetric Tree, Easy

1. 문제

• 이진 트리가 주어질 때, 루트 노드를 기준으로 양쪽 서브 트리가 대칭인 지 판별하라.

2. 해결

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isMirror(node1: TreeNode|null, node2: TreeNode|null) {
    if(!node1 && !node2) return true;
    if(!node1 || !node2) return false;
    if(node1.val !== node2.val) return false;

    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}

function isSymmetric(root: TreeNode | null): boolean {
    return isMirror(root.left, root.right)
};

• 처음엔 왼쪽은 각 서브 트리를 위한 배열에 값을 담아 배열의 내용의 내용을 비교하는 식으로 해결하려 했다.
• 이 방식은 추가 공간을 사용하고, 배열에 채운 뒤에 비교하기 때문에 성능이 좋지 않을 것 같았다.
• 결국 다른 해결 방법을 참고.
• 포인트는 이진 트리의 탐색을 루트 노드부터 시작하는 것이 아닌, 비교 대상인 양쪽 서브 트리의 시작점부터 재귀를 수행하는 것.