/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        // 根节点为空，则无子树，也无子节点，深度不可能大于1，则平衡
        if (root == null) {
            return true;
        }
        // 子树左右节点深度相减的绝对值大于1，则不平衡
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        // 子树左右节点都平衡，则平衡
        // 递归下去，只要子树左右节点深度相差不大于1，那么都会最终走到空节点处，都会为true，也就表示平衡
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 子树的左右节点是否平衡，从底向上最终会返回左右节点各自的深度
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}