리트코드 572번 Subtree of Another Tree

두 개의 트리를 주고 Root 트리에 subRoot 트리가 존재하면 True
아니면 False를 출력하는 프로그램을 작성하라는 것이였다.

1. 문제는 두가지 였다. 어떤 방식으로 트리를 순회할 것인가
- BFS를 써서 빠르게 subRoot의 
Root가 있는지 확인하는 방식을 채택했다

2. subRoot와 같은 Root가 있다면 
어떻게 같은지 확인 하는것도 BFS를 썼다
하지만 백트래킹을 쓴다면 더 빠르게 구현 가능할 것 같다

/**
 * 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 {
    static boolean flag;
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        int sRoot = subRoot.val;

        if(root.val != sRoot && root.left == null && root.right == null) return false;

        flag = false;
        
        BFS(root, subRoot);
        

        return flag;
    }
    static void BFS(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        ArrayList<TreeNode> tList = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode tn = queue.poll();
            if(tn.val == subRoot.val) {
                tList.add(tn);
            }
            if(tn.left != null) {
                queue.add(tn.left);
            }
            if(tn.right != null) {
                queue.add(tn.right);
            }
        }
        if(tList.size() != 0) {
            String ans = making(subRoot);

            for(TreeNode t : tList) {
                String cmp = making(t);
                if(ans.equals(cmp)) {
                    flag = true;
                    return;
                }
            }

        }   
    }
    static String making(TreeNode t) {
       Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        queue.add(t);
        while(!queue.isEmpty()) {
                TreeNode tn = queue.poll();
                if(tn != null) {
                    sb.append(tn.val);
                } else {
                    sb.append("null");
                }
                if(tn == null) {
                    continue;
                }
                queue.add(tn.left);
                queue.add(tn.right);
                
                
               
            }
        return sb.toString();
    }

}