package com.zhaochao.tree;

/**
 * Created by zhaochao on 17/1/24.
 * 平衡二叉树是指： 对于树中的每个节点，其左右孩子的高度差不超过1
 * 注意：是每一个节点都平衡才可以。
 *
 * 方法一： 递归法。 用一个DFS深度优先帮助函数求树的高度， 若其中一个节点不平衡，则返回-1,否则返回树的高度
 */


public class JudgeAVL {

    public boolean isAVL(TreeNode root) {

        if(root == null) {
            return true;
        }

        return getDepth(root) != -1;
    }

    public int getDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = getDepth(root.left);
        int right = getDepth(root.right);

        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(3);

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node3.left = node4;

        JudgeAVL test = new JudgeAVL();
        boolean result = test.isAVL(root);
        System.out.println("Is balanced tree : "+result);

    }
}