문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

이진 트리의 모든 leaves을 왼쪽에서 오른쪽 순서로 고려하면, leaves의 값은 leaf 값 순서를 형성한다.

예를 들어, 위의 트리가 주어졌을 때, leaf 값 순서는 (6, 7, 4, 9, 8)이다.
두 이진 트리가 leaf 값 순서가 같다면 leaf는 유사한 것으로 간주한다.
주어진 두 트리 root1과 root2가 주어지고 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

#2

Input: root1 = [1, 2, 3], root2 = [1, 3, 2]
Output: false

Constraints

• 각 트리의 노드 수는 [1, 200] 범위에 있다.
• 주어진 트리 둘다 [0, 200] 범위의 값을 가진다.

Solved

/**
 * 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> leafValues1 = new ArrayList<>();
        List<Integer> leafValues2 = new ArrayList<>();

        collectLeaf(root1, leafValues1);
        collectLeaf(root2, leafValues2);

        return leafValues1.equals(leafValues2);
    }

    private void collectLeaf(TreeNode root, List<Integer> leafValues){
        if(root == null){
            return;
        }

        if(root.left == null && root.right == null){
            leafValues.add(root.val);
        }

        collectLeaf(root.left, leafValues);
        collectLeaf(root.right, leafValues);
    }
}