剑指 Offer.II-平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        // 计算保证所有子树都是平衡二叉树
        // 计算根节点 左右子树高度是否符合平衡二叉树的条件
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
	
    // 使用后序遍历计算当前树节点的深度
    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        // 判断左子树是否满足条件
        int left = recur(root.left);
        // 若左子树不满足条件 对其进行剪枝 提前返回
        if(left == -1) return -1;
        // 判断右子树是否满足条件
        int right = recur(root.right);
        // 若右子树不满足条件 对其进行剪枝 提前返回
        if(right == -1) return -1;
        // 若当前子树正常 判断左右节点的高度是否符合要求 若符合 正常返回高度 若不符合 直接返回-1 在上层调用中触发剪枝
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}