LeetCode 872. Leaf-Similar Trees




플랫폼: LeetCode
번호: 872
제목: 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]
두 시퀀스가 다릅니다.
두 트리가 "Leaf-Similar"한지 확인하려면, 각 트리의 리프 노드 값들을 왼쪽에서 오른쪽 순서대로 추출하여 만들어진 시퀀스를 비교해야 합니다. 이를 위해 다음과 같은 단계를 따를 수 있습니다.
리프 노드 시퀀스 추출:
각 트리에 대해 깊이 우선 탐색(DFS)을 수행하여 모든 노드를 방문합니다.
DFS 과정 중, 현재 방문한 노드가 리프 노드인지 확인합니다. (즉, 왼쪽 자식과 오른쪽 자식이 모두 없는지 확인)
만약 리프 노드라면, 그 노드의 값을 별도의 리스트(예: leaves)에 순서대로 추가합니다. DFS를 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 진행하면 자연스럽게 리프 노드들이 왼쪽에서 오른쪽 순서로 리스트에 담기게 됩니다.
시퀀스 비교:
첫 번째 트리(root1)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves1)를 얻습니다.
두 번째 트리(root2)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves2)를 얻습니다.
두 리스트 leaves1과 leaves2가 완전히 동일한지 비교합니다 (leaves1 ==...
