[LeetCode] Leaf-Similar Trees

binary tree 의 이파리 노드들을 생각할 때 왼쪽에서 오른쪽 순서로 이파리 노드들의 순서를 leaf value sequence 라고 한다

예를 들어 위 트리의 이파리노드들의 leaf value sequence는 (6, 7, 4, 9, 8) 이 된다고 한다

두개의 binary tree가 주어질 때 leaf value sequence가 같으면 true를 반환 하는 문제이다

Example 을 보자

만약 2번 예시와 같이 [2, 3] , [3, 2] 순서가 다르다면 false를 리턴해야 한다

const leafSimilar = function (root1, root2) {
  let leaf1 = [];
  let leaf2 = [];

  const helper = (root, array) => {
    if (root) {
      if (root.right === null && root.left === null) {
        return array.push(root.val);
      }
      helper(root.left, array);
      helper(root.right, array);
    }
  };

  helper(root1, leaf1);
  helper(root2, leaf2);

  return leaf1.toString() === leaf2.toString() ? true : false;
};

먼저 helper 함수를 만들기로 했다

helper 함수는 root 와 array를 파라미터로 받는데 현재 노드가 null이 아닐 때 현재 노드가 이파리 노드라면 array에 push를 해주기로 했고 만약 이파리노드가 아니라면 현재 노드의 왼쪽 자식과 오른쪽 자식을 root로 재귀를 돌려주기로 했다

helper 함수에 파라미터로 root1, leaf1 , root2, leaf2 를 넣어주어 각 트리의 이파리 노드의 leaf value sequence 배열을 만들어 주었다

그 다음 두 배열을 비교하여 같으면 true 틀리면 false를 리턴해준다

배열은 비교를 할때 toString 메소드를 사용하여 문자열로 바꾼뒤에 해주었다. 그대로 배열끼리 비교를 해버리면 주소값을 비교하기 때문에 무조건 false가 나온다

submit을 해보니

정답이었다!