55-II.平衡二叉树 #

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        // 注意 isBalanced(root.left) && isBalanced(root.right) 
        // 题目是要求任意节点的左右子树的深度相差不超过1
        // 所以需要左右子树也是平衡树
        return Math.abs(dfs(root.left) - dfs(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int dfs(TreeNode root){
        // base case
        if(root == null) return 0;
		// 获得左右子树的层数，比较大小，取大者，+1
        return Math.max(dfs(root.left),dfs(root.right)) + 1;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 如果height(root)为-1，则不是平衡树，如果是返回树的高度
        return height(root) >= 0;
    }
    public int height(TreeNode root){
        // base case
        if(root == null) return 0;
        // 获取左右子树的高度
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        // -1表示不是平衡树
        // 如果左或右子树不是平衡树，或者左右子树的差值大于1，说明该树不是平衡树，返回-1
        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        // 是的话，返回树的高度
        return Math.max(leftHeight,rightHeight) + 1;
    }
}