110. Balanced Binary Tree.md

Solution1 （dfs）

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = dfs(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = dfs(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        int height = Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight);
        return height == - 1 ? -1 : height + 1;
    }
}

note

• time O(N) space O(1)
• The idea is to use -1 as a flag to indicate height difference being more than 1. At each level, we will check if returned left or right tree's height is -1. If it is -1 which means we have already found unbalanced subtree, we return -1 to the last call and it will get returned to the root call. Otherwise, we return 1 + max(left, right).