[Leetcode] 101. Symmetric Tree -JS

https://leetcode.com/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 중심을 기준으로 거울처럼 대칭인지 판단하라.

제한조건
--------------------
- 이진트리 노드의 갯수는 1 ~ 1000이다.
- -100 <= Node.val <= 100

 

2. 접근 방법

접근방법
--------------------
재귀사용해서 left와 right가 대칭인지 비교한다.

대칭 조건
1. left, right 둘다 null이면 대칭
2. left, right의 val 동일하면 대칭

left, right 대칭인지 분간하고 이어서 판단해야할 것은 left, right의 자식 node들이다.

자식 node들이 대칭인지 확인하려면 다음과 같이 비교해야한다.

자식 대칭 조건
1. left.left, right.right가 대칭이어야 함
2. left.right, right.left가 대칭이어야 함

즉, 자식들을 재귀 함수로 호출하고 그 반환값으로 대칭인지 아닌지 확인한다.

 

 

3. 코드

/**
 * 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)
 * }
 */
var isSymmetric = function(root) {
    if (!root) {
        return true;
    }

    function isMirror(left, right) {
        if (!left && !right) return true; // 둘다 null 이면 대칭
        if (!left || !right) return false; // 하나만 null 이면 비대칭
        if (left.val !== right.val) return false; // 값이 다르면 비대칭
        
        // left, right의 자식 노드가 존재하니 더 깊이 확인해봐야함
        // left의 left 와 right의 right 대칭 비교 && left의 right 와 right의 left 대칭 비교
        return isMirror(left.left, right.right) && isMirror(left.right, right.left)
    }
    return isMirror(root.left, root.right);
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(log n ~ n) 좌우 균형을 이룰 경우: log n, 편향된 경우: n

 

이전에 풀었던 문제들은 제출하는 함수 자체로 재귀함수를 구현했는데, 이번 문제는 재귀 함수를 따로 선언하고

선언한 함수를 통해서 문제의 조건을 판단하였다.

 

left, right가 대칭인지 비교한 뒤 대칭으로 판별되면 재귀 함수를 자식들의 left, right로 호출하여 검사한다.

 

재귀함수를 1번만 호출하는 것이 아닌 2번 호출하여 두 호출값이 && 논리연산자로 값을 반환하는 방법이 생소했다.

자주 풀어보면 익숙해질 것 같다.