[LeetCode] 100. Same Tree 풀이 (JS)

0. 문제

https://leetcode.com/problems/same-tree/submissions/

Same Tree - LeetCode

입력값 두 이진 트리가 구조적으로 동일하고 노드가 동일한 값을 갖는 경우 true를 출력 아닐 경우 false를 출력한다.

두 개의 이진 트리가 구조적으로 동일하고 노드가 동일한 값을 갖는 경우 동일한 것으로 간주된다.

#1
Input: p = [1,2,3], q = [1,2,3]
Output: true

#2
Input: p = [1,2], q = [1,null,2]
Output: false

#3
Input: p = [1,2,1], q = [1,1,2]
Output: false

 

1.언어

자바스크립트(JavaScript)

 

2. 문제 풀이

var isSameTree = function(p, q) {
    if (p == null && q == null) return true;
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) &&
        isSameTree(p.left, q.left);
};

Runtime: 77 ms, faster than 65.90% of JavaScript online submissions for Same Tree.

Memory Usage: 42.4 MB, less than 36.69% of JavaScript online submissions for Same Tree.

 

재귀 알고리즘을 사용했다. 두 트리의 오른쪽 노드를 한 지점씩 검사한다.

각 val 값과 트리의 길이가 동일한지 판별하고

오른쪽 노드 검사가 끝나면 왼쪽도 동일하게 검사하며 다른 부분이 있을 경우 false 를 반환한다.