Problem

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example
Given binary tree A = {3,9,20,#,#,15,7}, B = {3,#,20,15,7}

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
The binary tree A is a height-balanced binary tree, but B is not.

思路

1. 我们需要的信息,
   1. 左子树是否平衡, 右子树是否平衡
   2. 左右子树的深度差是否小于1
   3. 所以定义一个class包含这些需要返回的信息

    public boolean isBalanced(TreeNode root) {
        return helper(root).isBalanced;
    }

    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, true);
        }
        Result left = helper(root.left);
        Result right = helper(root.right);

        int depth = Math.max(left.depth, right.depth) + 1;
        if (!left.isBalanced || !right.isBalanced) {
            return new Result(depth, false);
        }

        if (Math.abs(left.depth - right.depth) > 1) {
            return new Result(depth, false);
        }

        return new Result(depth, true);
    }

    class Result {
        int depth;
        boolean isBalanced;

        public Result(int depth, boolean isBalanced) {
            this.depth = depth;
            this.isBalanced = isBalanced;
        }
    }