图解LeetCode——剑指 Offer 55 - II. 判断是否是平衡二叉树

一、题

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

二、示例

2.1> 示例 1：

【输入】root = [3,9,20,null,null,15,7] 【输出】true

2.2> 示例 2：

【输入】root = [1,2,2,3,3,null,null,4,4] 【输出】false

2.3> 示例 3：

【输入】root = [] 【输出】true

提示：

• • 0 <= 树的结点个数 <= 10000

三、解题思路

根据题目描述，我们要通过遍历二叉树的节点来获取任意节点的左右子树的深度，然后如果发现，只要这个深度之差超过1了，那么就不是平衡二叉树了。其实本题的解法，与《剑指 Offer 55 - I. 二叉树的深度》这道题基本类似，只是多了一个步骤，即：用于校验左右子树的深度差而已。

下面我们采用深度遍历的方式来解题，由于二叉树的深度是需要根据左子树深度和右子树深度进行差值计算来判断是否大于1，所以我们采用深度遍历中的后序遍历方式，即：先遍历左子树，然后遍历右子树，最后遍历子树的根节点。那么它的代码模型是这样的：

public void dfs(TreeNode node) {
    ... ...
    dfs(root.left); // 遍历左子树
    dfs(root.right); // 遍历右子树
    node // 遍历根节点
    ... ...    
}

除了上面的遍历方式外，我们可以创建一个全局变量boolean isBalanced，默认值为true，用于表示当前二叉树是否为平衡二叉树。那么在遍历过程中，我们的中断条件有如下两种情况，即：

【情况1】在dfs(...)方法中，传入的Node为空，则直接结束当前这个分支的遍历。 【情况2】当发现isBalanced等于false的时候，则直接结束当前这个分支的遍历。

上面就是本道题的解题思路了。还是按照惯例，下面我们以输入root = [1,2,2,3,3,null,null,4,4]为例，看一下具体的处理过程。请见下图所示：

四、代码实现

class Solution {
    boolean isBalanced = true;
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return isBalanced;
    }
    public int dfs(TreeNode node) {
        if (node == null || !isBalanced) return 0;
        int lDepth = dfs(node.left);
        int rDepth = dfs(node.right);
        if (Math.abs(lDepth - rDepth) > 1) isBalanced = false;
        return Math.max(lDepth + 1, rDepth + 1);
    }
}