[LeetCode] Leaf-Similar Trees

1.문제

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

두개의 이진 트리가 주어질 때 각 트리의 이파리 노드의 값을 배열에 왼쪽부터 오른쪽 순서대로 넣었을 때 같은 배열인지를 판단하는 문제이다.

Example 1

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Constraints:

• The number of nodes in each tree will be in the range [1, 200].
• Both of the given trees will have values in the range [0, 200].

2.풀이

1. 트리를 순회하면서 이파리 노드이면 배열에 저장한다.
2. 저장한 두 배열의 요소 값들이 같은지 체크한다.

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
const leafSimilar = function (root1, root2) {
  const result1 = [];
  const result2 = [];

  // 이파리 노드이면 배열에 이파리 노드의 value를 넣는다
  const helper = (root, result) => {
    if (!root) return;
    if (!root.left && !root.right) {
      result.push(root.val);
      return;
    }

    helper(root.left, result);
    helper(root.right, result);
  };

  helper(root1, result1);
  helper(root2, result2);

  // 만약 두 배열의 길이가 다르면 fasle
  if (result1.length !== result2.length) return false;

  // 두 배열의 요소를 비교해서 같은지 판단한다.
  for (let i = 0; i < result1.length; i++) {
    if (result1[i] !== result2[i]) {
      return false;
    }
  }

  return true;
};

3.결과