문제 // 자료구조 // 트리(Tree) // 공통조상 // toJava

/**
 * [첫번째 공통 조상]
 *  이진트리에서 노드 두개가 주어졌을때,
 *  이 두 노드의 첫번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성
 *  자료구조내에 추가로 노드를 저장해선 안된다.
 *
 * [풀이]
 *  => 주어진 두 노드가 같은 레벨인가요 ?
 *      => 같은 레벨이 아니라면 높이의 차이를 구해서 처리
 *  => 노드가 부모의 참조를 가질 수 있나요 ?
 *      => 부모에 대한 참조가 없을때 해결할 수 있을까 ?
 *          => * 있음 - NodeA와 NodeB가 더이상 같은쪽에 있지 않으면 그것이 공통조상
 * */
public class Q08 {

    /* main */
    public static void main(String[] args) {

        // @Test - 부모참조 있을때
        Node rootB = new Node(4);
        rootB.left = new Node(2);
        rootB.left.parent = rootB;
        rootB.right = new Node(6);
        rootB.right.parent = rootB;
        rootB.left.left = new Node(1);
        rootB.left.left.parent = rootB.left;
        rootB.left.right = new Node(3);
        rootB.left.right.parent = rootB.left;
        rootB.right.left = new Node(5);
        rootB.right.left.parent = rootB.right;
        rootB.right.right = new Node(7);
        rootB.right.right.parent = rootB.right;
        System.out.println(findSamePredecessorA(rootB.right.right/*7*/, rootB.left.left/*1*/).data); // -> 4

        // @Test - 부모참조 없을때
        Node rootA = new Node(4);
        rootA.left = new Node(2);
        rootA.right = new Node(6);
        rootA.left.left = new Node(1);
        rootA.left.right = new Node(3);
        rootA.right.left = new Node(5);
        rootA.right.right = new Node(7);
        System.out.println(findSamePredecessorB(rootA, rootA.right.right/*7*/, rootA.left.left/*1*/).data); // -> 4
    }

    /* Node */
    static class Node {
        int data;
        Node parent;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    /* findSamePredecessorA - 부모참조 있을때 */
    public static Node findSamePredecessorA( Node nodeA, Node nodeB ) {
        int depthA = getDepth( nodeA );
        int depthB = getDepth( nodeB );
        if( depthA > depthB ) {
            // == A가 더 깊다 (A를 올림) ==
            upStep(nodeA, depthA - depthB);
        }
        else if( depthA < depthB) {
            // == B가 더 깊다 (B를 올림) ==
            upStep(nodeB, depthB - depthA);
        }

        while ( nodeA != nodeB && nodeA != null & nodeB != null ) {
            nodeA = nodeA.parent;
            nodeB = nodeB.parent;
        }
        return nodeA == null || nodeB == null ? null : nodeA;
    }

    /* getDepth */
    public static int getDepth( Node node ) {
        int depth = 0;
        while ( node != null ) {
            node = node.parent;
            depth ++;
        }
        return depth;
    }

    /* upStep */
    public static Node upStep( Node node, int step ) {
        for (int i = 0; i < step; i++) {
            node = node.parent;
        }
        return node;
    }

    /* findSamePredecessorB - 부모참조 없을때 */
    public static Node findSamePredecessorB( Node root, Node a, Node b ) {
        boolean isLeftA = checkDirection(root.left, a);
        boolean isLeftB = checkDirection(root.left, b);
        if(isLeftA != isLeftB) {
            return root;
        } else {
            if(isLeftA) {
                // == 둘다왼쪽 ==
                return findSamePredecessorB(root.left, a, b);
            } else {
                // == 둘다오른쪽 ==
                return findSamePredecessorB(root.right, a, b);
            }
        }
    }

    /* checkDirection  */
    public static boolean checkDirection( Node root, Node target ) {
        if(root == null) return false;
        if(root == target) return true; // 이쪽에있어요 !
        return checkDirection(root.left, target) || checkDirection(root.right, target);
    }

}