솔루션 개발:

질문 설명

따라서 이진 트리가 주어지고 대칭 트리인지 확인해야 합니다. 나무에서 보면 거울이어야 한다는 뜻이다. 미러가 없기 때문에 주어진 루트 노드를 확인할 필요가 없습니다. 그러나 왼쪽과 오른쪽 자식은 미러링해야 합니다.

미러링된 의미는 트리의 left 쪽에서 트리의 right 쪽이 동일한 값을 갖지만 자식이 서로 바뀌어야 한다는 것입니다. 그것은 혼란스럽게 들리고 조금 있습니다. 시각적으로 말하면 상상하기 쉽지만 이것을 코드로 나타내려면 조금 더 복잡합니다.

권장 지식

Binary Trees

Binary Tree Traversals

Post Order Traversal

Javascript Call Stack

우리는 무엇을 알고 있습니까?

이진 트리가 있고 대칭 트리인지 확인해야 합니다. 그 의미는 나무에서 거울의 것이 되어야 한다는 것입니다. 미러가 없기 때문에 주어진 루트 노드를 확인할 필요가 없습니다. 그러나 왼쪽과 오른쪽 자식은 미러링해야 합니다.

우리는 주어진 노드에서 그 자식이 같은 값을 가져야 하지만 그들의 자식이 서로 바뀌어야 한다는 것을 알고 있습니다. 한쪽은 왼쪽에 있고 다른 쪽은 오른쪽에 있다는 의미입니다.

어떻게 할 것인가:

트리의 양쪽에서 동시에 사후 순회를 수행할 것입니다. 즉, 왼쪽에서는 최대한 왼쪽으로 가고 오른쪽에서는 최대한 오른쪽으로 갑니다. 양쪽 노드의 값을 비교하십시오. 그들이 같다면 우리는 괜찮습니다. 그렇지 않다면 우리는 그것이 나쁜 나무라는 것을 압니다.

우리는 이것을 재귀적으로 할 것입니다.

첫째, 모든 노드를 모두 동일한 것처럼 취급해야 합니다. 모든 노드에 동일한 프로세스를 적용한다는 의미입니다. 먼저 왼쪽 트리와 오른쪽 트리의 노드가 비어 있는지 묻습니다. 이 경우 오류 없이 이진 트리의 끝에 도달했음을 의미합니다. 대칭 트리라는 의미입니다.

그런 다음 '왼쪽 및 오른쪽 트리가 모두 비어 있지 않습니까?'라고 묻습니다. 그 중 하나는 리프 노드가 아니고 다른 하나는 리프 노드임을 의미합니다. 이것이 사실이라면 우리는 그것이 나쁜 나무라는 것을 압니다. 그래서 우리는 돌아갑니다 false

그런 다음 두 트리의 값을 비교합니다. '현재 왼쪽 값이 현재 오른쪽 값과 같은가요?' 이 경우 대칭 노드가 있습니다. 그렇지 않은 경우 반환합니다false.

그런 다음 트리가 소진될 때까지 오른쪽 및 왼쪽 트리를 계속 검색합니다. 가능한 모든 노드를 방문했음을 의미합니다.

모든 nodes를 방문하면 나무가 대칭인지 묻습니다. 모든 노드를 방문했고 대칭인지 확인했음을 의미합니다. 그렇다면 true 를 반환합니다. 그렇지 않은 경우 false를 반환합니다. 어디에서나 false가 발생하면 스택을 통해 버블링되어 잘못된 노드가 있으므로 이것은 잘못된 트리임을 알려줍니다. 모두 참이면 true 를 반환합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 트리에 있는 노드 수 | 우리는 항상 전체 트리를 탐색하므로

공간 복잡도: O(h) | 호출 스택을 사용하여 노드를 저장하므로 | 하지만 최악의 경우와 같이 공간 복잡도가 **O(n)**이라고 주장할 수 있지만 호출 스택에는 트리가 가진 만큼의 노드n가 포함됩니다.

' 개선될 수 있을까? ' 예! Morris Traversal은 O(1) 공간 복잡성에서 이 문제를 해결할 수 있습니다. 그러나 Morris Traversal은 읽기 까다롭고 어렵습니다. 단순화를 위해 여기서는 사용하지 않습니다.

리트코드 결과:

제출 링크 참조:

런타임: 대칭 트리에 대한 JavaScript 온라인 제출의 96.46%보다 63ms 빠름

메모리 사용량: 55.6MB, 대칭 트리에 대한 JavaScript 온라인 제출의 44.80% 미만

해결책

var isSymmetric = function (left_tree, right_tree = left_tree) {

    /* -------------------------------------------------------------------------- */
    /*                             101. Symmetric Tree                            */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
    */

     // https://leetcode.com/submissions/detail/684314946/

    // Both are trees are the same
    if (!left_tree && !right_tree) {
        return true;
    }

    // One exists without another?
    if (!left_tree || !right_tree) {
        return false;
    }

    // Are left and right of same value?
    // If not return false
    if (left_tree.val != right_tree.val) {
        return false;
    }

    // Do all the left trees and right trees
    let outer_tree = isSymmetric(left_tree.left,  right_tree.right);
    let inner_tree = isSymmetric(left_tree.right, right_tree.left);

    // Are both trees the same?
    return outer_tree && inner_tree;
};