剑指 Offer 55 - II. 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路

这题可以用分治法解决。
判断一个root是不是平衡二叉树，条件如下

1. 左子树是平衡二叉树
2. 右子树是平衡二叉树
3. 左右子树的高度差不超过1

由于java只能返回一个参数，所以我们可以声明一个ResultType类型，储存一个节点是否是平衡二叉树以及它的高度。

class Solution {
    static class ResultType {
        boolean isBalanced;
        int depth;

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

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

    public ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, 0);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        if (left.isBalanced &&
                right.isBalanced &&
                Math.abs(left.depth - right.depth) <= 1) {
            return new ResultType(true, Math.max(left.depth, right.depth) + 1);
        }
        return new ResultType(false, -1);
    }
}