[Dart] 872. Leaf-Similar Trees

1. 문제

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75

 

 

 

2. 요구사항

1) 두 개의 이진 트리 root1과 root2가 주어진다.

2) 이 두 개의 이진 트리가 leaf-similar 트리인지 확인한다.

3) leaf-similar 트리란 두 트리의 리프 노드들이 왼쪽에서 오른쪽 순서로 동일한 값을 가지는 것을 의미한다.

4) 리프 노드란 자식이 없는 노드이다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */

class Solution {
  /// 두 개의 이진 트리의 리프 노드가 같은지 비교
  bool leafSimilar(TreeNode? root1, TreeNode? root2) {
    List<int> list1 = searchLeafTree(root1);  // 첫 번째 트리의 리프 노드 리스트
    List<int> list2 = searchLeafTree(root2);  // 두 번째 트리의 리프 노드 리스트

    // 길이가 다르면 false
    if (list1.length != list2.length) return false;

    // 값 비교
    for (int i = 0; i < list1.length; i++) {
      if (list1[i] != list2[i]) return false;
    }

    return true;
  }

  /// 이진 트리에서 리프 노드들의 값을 리스트로 반환
  List<int> searchLeafTree(TreeNode? root) {
    List<int> leafNodeList = [];

    // DFS(깊이 우선 탐색) 재귀 함수
    void dfs(TreeNode? node) {
      if (node == null) return;

      // 리프 노드일 경우 리스트에 추가
      if (node.left == null && node.right == null) {
        leafNodeList.add(node.val);
      }

      // 좌우 자식 순회
      dfs(node.left); 
      dfs(node.right);
    }

    dfs(root);

    return leafNodeList;
  }
}