872. Leaf-Similar Trees

Leaf-Similar Trees - LeetCode

이진 트리의 모든 잎을 왼쪽에서 오른쪽 순서로 고려할 때, 이러한 잎의 값은 잎 값 시퀀스를 형성합니다.
예를 들어, 위에 제시된 트리의 경우, 잎 값 시퀀스는 (6, 7, 4, 9, 8)입니다.
두 이진 트리가 동일한 잎 값 시퀀스를 가지고 있다면, 이 두 트리는 잎 동일한 것으로 간주됩니다.
만약 주어진 두 개의 트리인 root1과 root2의 루트 노드가 잎 동일하다면 true를 반환하십시오.

 

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

문제 요약

두 주어진 이진 트리의 리프 노드 값 순서가 동일한지 여부를 판단합니다.

 

풀이과정

주어진 두 이진 트리의 리프 노드를 순회하고, 순회한 리프 노드 값들을 비교하여 동일한지 여부를 확인해야 합니다. 이를 위해 깊이 우선 탐색(DFS)을 사용할 수 있습니다.

1. 먼저, 주어진 두 트리의 리프 노드 값을 저장할 두 개의 리스트를 생성합니다.
2. DFS를 사용하여 첫 번째 트리(root1)의 리프 노드 값을 순회하고, 순회 중인 노드가 리프 노드일 때 해당 값을 리스트에 추가합니다.
3. 두 번째 트리(root2)에 대해서도 동일한 과정을 수행하여 두 번째 리스트에 리프 노드 값을 추가합니다.
4. 두 리스트를 비교하여 값이 동일하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        dfs(root1, list1);
        dfs(root2, list2);
        
        return list1.equals(list2);
    }
    
    private void dfs(TreeNode node, List<Integer> list) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            list.add(node.val);
        }
        
        dfs(node.left, list);
        dfs(node.right, list);
    }
}