leetcode 872, Leaf-Similar Trees

들어가는 말

두 트리의 단말 노드의 개수와 순서가 같으면 true를, 다르면 false를 반환하는 문제다.
처음에는 두 트리를 함께 DFS로 돌려서 확인하려 했지만, 단말 노드가 같으나 부모 노드가 다른 경우가 있어서 따로따로 돌려서 비교해줬다.

코드 설명

1. 일단 단말 노드를 넣을 리스트(순서가 유지가 되어야 하니 LinkedList를 이용한다)를 생성한다.
2. dfs로 각각의 트리를 돌려준다.
   2-1 만일 왼쪽 노드와 오른쪽 노드가 없어 단말 노드일 경우에는 주어진 리스트에 val을 넣고 return한다.
   2-2 왼쪽 노드가 존재한다면 왼쪽 노드를 탐색한다.
   2-3 오른쪽 노드가 존재한다면 오른쪽 노드를 탐색한다.
3. 각각의 트리의 단말 노드를 넣은 리스트가 같은지를 확인해서 같으면 true를, 다르면 false를 반환한다.
   처음에는 반복문을 돌려서 확인해줬지만 리스트에 두 리스트가 같은지를 확인하는 equals 메소드가 있으니 이를 이용했다. 단순한 '=='로는 비교가 불가능하다('=='는 주소를 확인해 주는 거라 그럼. String도 마찬가지)

코드

/**
 * 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 LinkedList<>();
        List<Integer> list2 = new LinkedList<>();

        dfs(root1, list1);
        dfs(root2, list2);

        return list1.equals(list2);

    }

    public void dfs(TreeNode node, List<Integer> list){

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

        if(node.left != null){
            dfs(node.left, list);
        }

        if(node.right != null){
            dfs(node.right, list);
        }


    }
}

링크

https://leetcode.com/problems/leaf-similar-trees/description/