[leetCode/JS] 872. Leaf-Similar Trees

난이도 [ 😊 ] Easy

 

문제 설명

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.

 

2개의 2진 트리가 주어진다. 각 트리마다 마지막 leaf 가 순서와 값이 같을 때 true를 넘긴다.

 

입출력 예

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].

 

---

 

내 솔루션

• 당연히 기본적인 DFS 방식으로 풀어야한다.
• left, right가 존재하면 dfs()를 호출하고 둘다 값이 없는 마지막 Leaf 일 때, nodes에 `/${node.val}` 로 저장한다.
• /가 필요한 이유는 1,2,3 과 12,3이 같은 값이 되기 때문.

var leafSimilar = function(root1, root2) {
  const getLastNode = (root) => {
    let nodes = '';
    const dfs = (node) => {
      if(node.left) dfs(node.left)
      if(node.right) dfs(node.right)
      if(!node.left && !node.right) nodes += `/${node.val}`
    }
    dfs(root);
    return nodes;
  }
  return getLastNode(root1) === getLastNode(root2);
};

 

감상평

• easy 문제일 수록 답은 하나로 귀결될 수 밖에 없나보다 다른 사람들의 솔루션도 비슷한 방식이다.
• 메모리는 조금 많이 사용했다. 왜지! 더 적은 메모리를 사용한 솔루션을 봐도 무거워보이는데..
• 하지만 빨랐죠?