문제 // 자료구조 // 트리(Tree) // 하위트리확인 // toJava

/**
 * [하위트리확인]
 *  두개의 커다란 이진트리 T1, T2가 있을때
 *  T1이 T2보다 훨씬 크다고 했을때, T2가 T1의 하위 트리 (sub tree)인지 판변하는 알고리즘 제자
 *
 * [풀이]
 *  => 플래그를 이용하는 방법
 *  => 이동하는 모든 플래그에 대해서 기호값으로 배열에 추가
 *  => 중위순회 & 전휘순회 & 후위순회 상관없이 풀이가능
 *  => 플래그가 배열을 형태까지 복사하기 때문에 배열이 겹친다면 하위트리로 확인이 가능함
 *
 * */

public class Q10 {

    public static void main(String[] args) {
        // @Test
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);

        // == 플래그를 사용하는 방법 -> (풀이) ==
        useFlag(root);
        useFlag(root.left); // 해당부분이 위에 포함됨
        useFlag(root.right); // 해당부분이 위에 포함됨

        // == 플래그를 사용하는 방법 -> (정답) ==
        System.out.println(containsTree(root, root.left));
        System.out.println(containsTree(root, root.right));
    }

    /* Node */
    static class Node {
        // == Field ==
        int data;
        Node left;
        Node right;

        // == Constructor ==
        public Node(int data) {
            this.data = data;
        }

        // == toString ==
        public String toString() {
            // TODO
            return null;
        }
    }

    /* useFlag */
    static public List<String> useFlag(Node root) {
        List<String> list = new LinkedList<>();
        inorder(root, list);
        System.out.println(Arrays.toString(list.toArray(new String[list.size()])));
        return null;
    }

    /* inorder - 중위순회 In-order Traversal */
    public static void inorder(Node root, List<String> list) {
        if(root.left != null) {
            list.add("a"); // left down (a)
            inorder( root.left, list );
            list.add("d"); // left up (b)
        }
        list.add(root.data + "");      // middle
        if(root.left != null) {
            list.add("c"); // right down (c)
            inorder( root.right, list );   // right
            list.add("d"); // right up (d)
        }
    }

    /* containsTree */
    public static boolean containsTree(Node t1, Node t2) {
        StringBuffer string1 = new StringBuffer();
        StringBuffer string2 = new StringBuffer();
        getOrderString(t1, string1);
        getOrderString(t2, string2);
        return string1.indexOf(string2.toString()) != -1;
    }

    /* getOrderString */
    public static void getOrderString( Node node, StringBuffer sb ) {
        if( node == null) {
            sb.append("X");
            return;
        }
        sb.append(node.data + " ");
        getOrderString(node.left, sb);
        getOrderString(node.right, sb);
    }

}