LeetCode 872. Leaf-Similar Trees

🚀 문제: 872. Leaf-Similar Trees

• 플랫폼: LeetCode

• 번호: 872

• 제목: Leaf-Similar Trees

• 링크: https://leetcode.com/problems/leaf-similar-trees/

• 난이도: Easy

📝 문제 설명

두 개의 이진 트리 root1과 root2가 주어졌을 때, 이 두 트리가 잎이 비슷한(Leaf-Similar)지 확인하는 문제입니다.

두 트리가 잎이 비슷하다는 것은, 각 트리의 리프 노드(Leaf Node) 값들을 왼쪽에서 오른쪽 순서대로 나열했을 때, 그 순서열(Sequence)이 서로 동일하다는 것을 의미합니다.

• 리프 노드: 자식 노드가 없는 노드를 말합니다.

예시 1:

• 입력: 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]

     Tree 1:              Tree 2:
        3                   3
       / \                 / \
      5   1               5   1
     / \ / \             / \ / \
    6  2 9  8           6  7 4  2
      / \                   / \
     7   4                 9  8
  

• 출력: true

• 설명:

  • Tree 1의 리프 노드 값 시퀀스: [6, 7, 4, 9, 8]

  • Tree 2의 리프 노드 값 시퀀스: [6, 7, 4, 9, 8]

  • 두 시퀀스가 동일하므로 두 트리는 Leaf-Similar 합니다.

예시 2:

• 입력: root1 = [1, 2, 3], root2 = [1, 3, 2]

• 출력: false

• 설명:

  • Tree 1의 리프 노드 값 시퀀스: [2, 3]

  • Tree 2의 리프 노드 값 시퀀스: [3, 2]

  • 두 시퀀스가 다릅니다.

🤔 풀이 아이디어: DFS로 리프 노드 시퀀스 추출 후 비교

두 트리가 "Leaf-Similar"한지 확인하려면, 각 트리의 리프 노드 값들을 왼쪽에서 오른쪽 순서대로 추출하여 만들어진 시퀀스를 비교해야 합니다. 이를 위해 다음과 같은 단계를 따를 수 있습니다.

1. 리프 노드 시퀀스 추출:

   • 각 트리에 대해 깊이 우선 탐색(DFS)을 수행하여 모든 노드를 방문합니다.

   • DFS 과정 중, 현재 방문한 노드가 리프 노드인지 확인합니다. (즉, 왼쪽 자식과 오른쪽 자식이 모두 없는지 확인)

   • 만약 리프 노드라면, 그 노드의 값을 별도의 리스트(예: leaves)에 순서대로 추가합니다. DFS를 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 진행하면 자연스럽게 리프 노드들이 왼쪽에서 오른쪽 순서로 리스트에 담기게 됩니다.

2. 시퀀스 비교:

   • 첫 번째 트리(root1)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves1)를 얻습니다.

   • 두 번째 트리(root2)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves2)를 얻습니다.

   • 두 리스트 leaves1과 leaves2가 완전히 동일한지 비교합니다 (leaves1 ==...