문제 // 자료구조 // 트리(Tree) // 균형(트리높이) // toJava

/**
 * [균형확인]
 *  이진트리가 균형 잡혀있는지 확인하는 함수를 작성하라
 *  이 문제에서 균형잡힌 트리란
 *  모든 노드에 대해서 왼쪽부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미
 *
 * [풀이]
 *  => 균형잡힌 트리란 ?
 *  => 루트로 부터 왼쪽트리와 오른쪽트리의 높이를 말하는 것인지 ?
 *  => 왼쪽과 오른쪽의 높이 차이가 1이내면 균형잡힌 트리인 것인지 ?
 *  => 왼쪽의 최대 높이와 오른쪽의 최대 높이를 각가 구해야함
 * */
public class Q04 {

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

        // @Test
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        System.out.println("[height] " + getHeight(root));
        System.out.println("[balance] " + isBalanced(root));
    }

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

    /* getHeight */
    public static int getHeight(Node root) {
        if(root == null) return 0;
        return Math.max(getHeight(root.left), getHeight((root.right))) + 1;
    }

    /* isBalanced */
    public static boolean isBalanced(Node root) {
        if( root == null ) return true;
        int heightDiff = getHeight(root.left) - getHeight(root.right);
        if(Math.abs(heightDiff) > 1) {
            return false;
        } else {
            return isBalanced(root.left) && isBalanced(root.right);
        }
    }

}