面试题 04.04. 检查平衡性 #

题目 #

检查二叉树是否平衡
平衡二叉树的定义为: 任取一个节点，其两棵子树的高度差不超过 1

思路 #

递归 #

代码 #

递归 #

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { this.val = x; }
}
class Solution {
    public int depth(TreeNode root) {
        if (root == null) return 0;
        
        int leftDepth = depth(root.left);
        if (leftDepth == -1) return -1;
        
        int rightDepth = depth(root.right);
        if (rightDepth == -1) return -1;
        
        if (Math.abs(leftDepth - rightDepth) > 1) return -1;
        
        return 1 + Math.max(leftDepth, rightDepth);
    }
    public boolean isBalanced(TreeNode root) {
        return depth(root) == -1 ? false: true;
    }
}