剑指Offer（三十九）-- 平衡二叉树

秦怀杂货店

发布于 2022-02-15 13:58:07

2970

发布于 2022-02-15 13:58:07

文章被收录于专栏：技术杂货店

代码已经同步到仓库地址：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 图片都是draw.io，绘制，在/drawio文件夹下。

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

示例1

输入

{1,2,3,4,5,6,7}

返回值

true

思路以及解答

这道题沿用了上一道【树的深度】的思路，何为平衡二叉树，也就是树的左右两个子树的深度相差不超过1，而且同时左右子树也要是平衡二叉树。譬如下面这个就是二叉树：

而这个不是平衡二叉树，节点3的左子树深度为2，右子树深度为0，两个子树的深度相差2。而如果单纯从根节点1开始，看左右子树的深度的话，就会发现节点1左右两个子树的深度相差1，是符合平衡二叉树的原则的。这也是为什么我们除了判断根节点的左右子树高度差绝对值相差1，还需要分别判断左右两个子树是否也符合平衡二叉树的判定规则。

既然要判断整棵树，也要分别判断两个子树，那么想到的肯定就是递归。判断流程大致如下：

1. 判断根节点是否为null，为null直接返回true。
1. 根节点如果不为null，需要求出左子树的高度以及右子树的高度，如果两个相差大于1，则返回·false`。
1. 如果两个子树的深度相差小于等于1，就需要分别判断左，右子树是否为平衡树。也就是以左右两个子节点为根节点，从第1步开始执行。

PS：判断树的深度的分析在上一篇中，有兴趣自己了解一下，也是使用递归，貌似图片东西多了就有点模糊，我的图片都是使用开源软件draw.io来画的，我会将源文件都开源在github中，画得丑见谅，后续有时间再完善了。

代码如下：

/**
 * @author wenhaoxu
 * @date 2021/1/29 14:48
 */
public class Solution39 {
    // 测试代码
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);

        treeNode.left.left =new TreeNode(4);
        treeNode.left.right = new TreeNode(5);
        treeNode.right.left = new TreeNode(6);
        treeNode.right.right = new TreeNode(7);
        Solution39 solution39 = new Solution39();
        boolean result = solution39.IsBalanced_Solution(treeNode);
        System.out.println(result);
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root != null) {
            int left = deep(root.left);
            int right = deep(root.right);
            if (Math.abs(left - right) > 1) {
                return false;
            } else {
                return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
            }
        }
        return true;
    }
    // 求树的深度
    public int deep(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(deep(node.left), deep(node.right)) + 1;
    }
}

class TreeNode {
    int val;
    public TreeNode left;
    public TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

【作者简介】：秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~ - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-29，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树