[LeetCode] 100. Same Tree

Lucid·2021년 2월 22일
1

문제

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

문제 접근 및 풀이

dfs와 bfs와 같은 search 문제가 약하기 때문에 해당 유형의 문제를 찾아서 가장 쉬운 문제부터 다져보기 위해 100번 문제를 선택했다.
처음 들었던 생각은 그냥 배열 비교 아닌가? 라는 생각이 들었다.
하지만 leetcode 자체에서 TreeNode를 입력값으로 주어지고 이를 사용해서 이진 트리로 풀어야 한다는 것을 확인했다.
해당 유형에 대한 풀이를 익히기 위해 solution을 참조하여 풀이하였다.

고려해야 할 사항

  1. 현재 p 노드가 null이고 q 노드가 null 이라면 둘이 현재 동일하기 때문에 true 반환
  2. p나 q의 노드가 null 이라면, 둘이 다르기 때문에 false 반환
  3. 그냥 둘이 다른 값이다 false 반환
  4. 나의 leftright 값이 비교 트리의 leftright 값과 동일한가 확인 (재귀)

결과

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

사담

!==!=이 런타임에서 10ms 이상의 차이가 났다. !== 이 10ms 빠름

profile
Find The Best Solution 😎

0개의 댓글