[Leetcode] 100. Same Tree - JS

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

 

1. 문제 분석

문제분석
--------------------
이진트리의 root인 p, q가 주어진다.
두 이진트리가 동일한지 판단하는 함수를 작성하라.
두 이진트리는 구조적으로 동일하고 node들의 값이 동일해야 동일하다.

제한조건
--------------------
- 이진트리의 node의 갯수는 0 ~ 100이다.
- -10^4 <= Node.val <= 10^4

 

2. 접근 방법

접근방법
--------------------
재귀로 생각해보자.

p,q의 val이 같은지 비교
    - 다르면 false를 반환
    - 같으면 p.left, q.left 재귀, p.right, q.right 재귀
결과값으로 left 재귀값, right 재귀값 모두 true면 true 아니면 false

 

 

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 isSameTree = function(p, q) {
    if (p === null && q === null) {
        return true;
    }
    if (p?.val !== q?.val) {
        return false;
    }

    const isLeftSame = isSameTree(p.left, q.left);
    const isRightSame = isSameTree(p.right, q.right);

    return isLeftSame && isRightSame;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(n)

 

이진 트리 문제를 풀 때 재귀를 고려하면 된다는 것을 알고 비슷한 문제를 풀어보니 이해가 잘되는 것 같다.

null 처리만 더 깔끔하게 해주면 좋을 것 같다.