(Tree, Easy) Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/

root와 subRoot 두 개의 트리가 주어졌을 때,
root 안에 subRoot 트리와 완전히 동일한 서브트리가 있는지 확인하는 문제다.
(당연히 인스턴스가 같은게 아니라, 구조와 노드 값들이 똑같은 것)

트리가 이진 탐색 트리도 아니고, 노드 val 자체도 중복해서 들어갈 수 있다는 전제가 있기 때문에..
subRoot의 val와 같은 모든 노드들을 찾아서 리스트에 넣어놓고 일일이 비교하는 로직을 짰다.

정답이 나오기는 하는데, 성능 결과를 보니 최선은 아닌 것 같다.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        // subRoot의 값과 같은 값을 가지는 노드들이 여러 개 있을 수 있으므로, 다 찾는다.
        int rootValue = subRoot.val;
        List<TreeNode> roots = new ArrayList<>();
        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);

        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node.val == rootValue) {
                roots.add(node);
            }

            if (node.left != null) {
                que.offer(node.left);
            }
            if (node.right != null) {
                que.offer(node.right);
            }
        }

        for (TreeNode node : roots) {
            if (dfs(node, subRoot)) {
                return true;
            }
        }

        return false;
    }

    private boolean dfs(TreeNode node, TreeNode subRoot) {
        if (node == null && subRoot == null) {
            return true;
        }
        if (node == null || subRoot == null) {
            return false;
        }
        if (node.val != subRoot.val) {
            return false;
        }

        return dfs(node.left, subRoot.left) && dfs(node.right, subRoot.right);
    }
}

그래서 개선하자면,
굳이 첫 while에서 모든 가능 후보들을 다 넣어놓고 추후에 돌리면서 판단할 필요 없이
즉시 즉시 같은 트리인지 판단하는게 반복 횟수를 더 줄일 수 있다.

왜? 기존 로직에서는 일단 트리 크기가 2000이라고 했을 때 2000번은 무조건 도는거고, 여기서 추가로 검사가 수행되는 건데.. val 값이 같을 때 즉시 검사를 하게 되면 2000번까지 가기 전에 이미 끝남

참고: 같은 트리인지 검사하는 로직은 여러 솔루션에서도 똑같이 쓰더라. 그런데 isSubtree 메서드 자체는 재귀 DFS로 풀어내는 사람이 많은 듯. 어쨌든 논리는 동일하니까.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        Queue<TreeNode> que = new ArrayDeque<>();
        que.offer(root);

        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node.val == subRoot.val && dfs(node, subRoot)) {
                return true;
            }

            if (node.left != null) {
                que.offer(node.left);
            }
            if (node.right != null) {
                que.offer(node.right);
            }
        }
        return false;
    }

    private boolean dfs(TreeNode node, TreeNode subRoot) {
        if (node == null && subRoot == null) {
            return true;
        }
        if (node == null || subRoot == null) {
            return false;
        }
        if (node.val != subRoot.val) {
            return false;
        }

        return dfs(node.left, subRoot.left) && dfs(node.right, subRoot.right);
    }
}