《剑指offer第二版》面试题55 题目二：平衡二叉树（java

题目描述

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

解题思路

1. 采用后续遍历的方式遍历每一个节点。
2. 遍历每个节点的时候记录他的深度，并判断每个节点是否是平衡的。

代码

class DepthHolder{
    int depth;
}

boolean isBalance(TreeNode root){
    DepthHolder holder = new DepthHolder();
    return isBalance(root, holder);
}

boolean isBalance(TreeNode node, DepthHolder holder){
    if (node == null) {
        holder.depth = 0;
        return true;
    }

    DepthHolder leftDepth = new DepthHolder();
    DepthHolder rightDepth = new DepthHolder();
    // 判断左子树是不是平衡的
    boolean isLBalance = isBalance(node.left, leftDepth);
    // 判断右子树是不是平衡的
    boolean isRBalance = isBalance(node.right, rightDepth);

    int diff = leftDepth.depth - rightDepth.depth;
    if (isLBalance && isRBalance && Math.abs(diff) <= 1) {
        // 当前节点是平衡二叉树，记录改节点的深度
        holder.depth = Math.max(leftDepth.depth, rightDepth.depth) + 1;
        return true;
    }
    return false;
}