Leetcode - 대칭 트리(JavaScript 포함)

오늘은 대칭 트리 알고리즘 문제를 해결하는 방법을 보여 드리겠습니다.

문제는 다음과 같습니다.


이 문제에서 우리는 이진 트리가 구조와 값에서 대칭인지 여부를 테스트해야 합니다. 그렇다면 질문은 언제 두 나무가 서로 거울 반사가 되는가입니다.

왼쪽 하위 트리가 오른쪽 하위 트리의 거울 반사면 트리는 대칭입니다. 트리 중간에 선을 그리면 트리가 자체적으로 접힐 수 있으며 해당 노드 값은 동일합니다.

이제 재귀적으로 해결하겠습니다.

1) 먼저 루트 노드를 확인합니다. null인 경우 추가 조치가 필요하지 않습니다. null이 아니면 재귀로 들어가 왼쪽 및 오른쪽 하위 트리를 모두 확인해야 합니다.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

2) 왼쪽 하위 트리와 오른쪽 하위 트리가 모두 null이면 대칭임을 의미합니다. 그 중 하나만 null이면 비대칭입니다.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;
}

3) 둘 다 null이 아닌 경우 해당 값을 확인해야 합니다. 동일하다면 노드의 왼쪽과 오른쪽으로 재귀를 계속할 것입니다. 왼쪽 하위 트리의 왼쪽 노드가 오른쪽 하위 트리의 오른쪽 노드와 동일하고 왼쪽 하위 트리의 오른쪽 노드가 오른쪽 하위 트리의 왼쪽 노드와 동일한지 확인해야 합니다.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;

    return (leftSub.val === rightSub.val 
            && isMirror(leftSub.left, rightSub.right) 
            && isMirror(leftSub.right, rightSub.left))
}