题⽬描述

输⼊⼀棵节点数为 n ⼆叉树，判断该⼆叉树是否是平衡⼆叉树。

在这⾥，我们只需要考虑其平衡性，不需要考虑其是不是排序⼆叉树

平衡⼆叉树（ Balanced Binary Tree ），具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过 1，并且左右两个⼦树都是⼀棵平衡⼆叉树。

样例解释：

思路及解答

自顶向下递归（基础解法）

平衡树意味着我们需要对⽐任何在同⼀个根下的左右⼦树的⾼度差，还记得之前我们计算树的⾼度么，使⽤递归⽅式来解决，其实这道题与算⾼度差不多，只是两边⾼度需要算出⼀个差值。

算法的主要思想：

  • 不断对⽐每两个节点的左右⼦树的最⼤⾼度差，注意取差的绝对值，需要⼩于等于1

  • 对⽐完左右⼦树之后，需要递归左⼦树以及右⼦树进⾏分别判断，都满⾜才是平衡树

  • 时间复杂度 O(nlogn) ：最差情况下，需要遍历树所有节点判断是否平衡，需要O(n)。但是判断每个节点最⼤⾼度需要递归左右⼦树，需要占⽤ O(log2n)，所以总共占⽤ O(Nlog2n)

  • 空间复杂度 O(n) ：最差情况下，也就是树退化为链表时，递归需要使⽤ O(n) 的栈空间，严格意义上递归栈也需要空间。

自底向上递归（优化解法）

上⾯的计算，仔细观察就会发现会有很多重复计算的过程，⽐如下⾯的数，计算⼦树深度的时候，计算 1 的左⼦树，和计算 2 的，基本都重复了。 应该如何避免这种重复计算呢？前⾯的是⾃顶向下的⽅式，因为每个节点都得把⼦树计算⼀遍才需要重复，如果我们从下往上计算，那不就避免了重复计算。后序遍历，先判断子树平衡性，再判断当前节点，对⽐逻辑如下：

  • 如果当前节点为空，⾼度为0

  • 如果当前节点的左⼦树的⾼度为-1，那么说明不平衡，否则，需要计算右⼦树⾼度，同样需要不等于-1，如果两者的差不符合⼩于等于1，那么说明它们不平衡，返回-1。通过这样 -1 异常值就会⼀路返回，到最初的调⽤处，得到不平衡的结果。

  • 时间复杂度 O(n) ：每个节点计算⼀次

  • 空间复杂度 O(n) ：递归需要使⽤额外堆栈空间

笔试面试时，建议首选这个方式，效率最优，代码简洁

封装信息法（面向对象思路）

通过自定义类同时返回高度和平衡信息，代码结构更清晰。