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

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

二、题目解析

判断一棵树是否是平衡树，首先第一步是要去获取它的左右子树的高度。

在获取高度的过程中，如果出现了某个节点的左右子树的高度差超过了 1 ，那也就意味着这个节点组成的子树不是平衡二叉树，更进一步，含有这个子树的二叉树也不是平衡二叉树。

因此，本题的操作如下：

1、自底向上判断，只要发现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了

2、递归的去计算当前节点的左子树高度，如果发现左子树是非平衡二叉树，直接返回这个结果而无需再去获取右子树的高度。

3、否则，递归的去计算当前节点的右子树高度，如果发现右子树是非平衡二叉树，直接返回这个结果而无需再去计算左右子树的高度差是多少。

4、否则计算一下当前节点 curNode 是否是平衡二叉树，即计算左右子树的高度差是否为 1。

5、再将如上的结果返回给它们的父节点，直到找到结果或者来到根节点为止。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution {
    public boolean isBalanced(TreeNode root) {
         // 自底向上判断，只要发现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
        return recur(root) != -1;
    }

    private int recur(TreeNode curNode) {
        
        // 递归终止条件
        // 如果当前节点 curNode 为空，那么高度就是 0
        if (curNode == null) return 0;

        // 递归的计算当前节点 curNode 的左子树高度
        int left = recur(curNode.left);

        // 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(left == -1) return -1;

        // 递归的计算当前节点 curNode 的右子树高度
        int right = recur(curNode.right);

        // 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(right == -1) return -1;

        // 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
        // 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
        // 因此计算一下当前节点 curNode 是否是平衡二叉树
        // 即计算 curNode 的左子树高度与右子树高度差
        // 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
        // 即节点 curNode 的左右子树中最大高度加 1 
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}