55(2)-判断是否是平衡二叉树

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

平衡二叉树的定义：如果二叉树中任意结点的左右子树的深度相差不超过1，那么就是平衡的二叉树。

我们可以使用求树的深度的方法。

 public boolean isBalanced(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean left = isBalanced(node.left);
        boolean right = isBalanced(node.right);

        return  left && right && Math.abs(maxDepth(node.left) - maxDepth(node.right)) <= 1 ;
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

我们还可以采用二叉树的后序遍历，同时将子树的高度一层一层的传递上来，这样可以省去重复计算。

public Pair<Boolean,Integer> isBalanced(TreeNode node, int depth) {
        if (node == null) {
            return new Pair<>(true, 0);
        }
        Pair<Boolean, Integer> left = isBalanced(node.left, depth);
        Pair<Boolean, Integer> right = isBalanced(node.right, depth);
        if (left.getKey() && right.getKey()) {
            int ldepth = left.getValue();
            int rdepth = right.getValue();
            if (Math.abs(ldepth - rdepth) > 1) {
                return new Pair<>(false, 0);
            }
            return new Pair<>(true, Math.max(ldepth, rdepth) + 1);
        }else{
            return new Pair<>(false, 0);
        }
    }