题解

解题思路

一看到树的题目就要想到使用递归解决问题，而且有时候可以通过使用递归、遍历等框架解题。

本题可以使用自顶向下的暴力法来遍历整棵树，时间复杂度相对较高

也可以使用自底向上的递归，最关键就是要阻断递归，递归到一定情况要结束当前节点递归，降低时间复杂度

方法一：暴力法：自顶向下

算法流程：
  • 通过比较每个节点的左右子树的最大高度差, 来判断此子树是否是二叉平衡树。
  • 若树的所有子树都平衡时，该树才是平衡二叉树。
Python 版本代码如下： 
class Solution:
    def IsBalanced_Solution(self, root: TreeNode) -> bool:
        if not root: return True
        # 高度差不能大于1，并且左右子树也是同样高度差要小于等于1
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)

    def depth(self, root):
        if not root: return 0
        # 左右子树中高度较大的作为当前节点高度
        return max(self.depth(root.left), self.depth(root.right)) + 1
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        return self.depth(pRoot)!=-1
    def depth(self,pRoot):
        if pRoot is None:
            return 0
        left = self.depth(pRoot.left)
        if left == -1:
            return -1
        right = self.depth(pRoot.right)
        if right == -1:
            return -1
        if (left-right) <-1&nbs***bsp;(left-right)>1:
            return -1
        else:
            return 1 + left if left>right else 1+right

复杂度分析：

时间复杂度 O(Nlog2N)：最差情况下，需要遍历树所有节点判断是否平衡，需要O(N)。判断每个节点最大高度需要递归左右子树，需要占用 O(log2N)，所以总共占用O(Nlog2N)
空间复杂度O(N)：最差情况下（树退化为链表时），递归需要使用O(N) 的栈空间。

方法二：自底向上递归

图解

算法流程：

  • 判断空树，题目要求空树也是平衡二叉树

  • 递归计算当前root左右子树的高度差

  • 注意：递归过程中有左/右子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点

  • 递归到底后，自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡

  • 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡

  • 递归终止条件：

    • root 为 null
    • 左右子树高度差大于1，即左右子树其中一个节点返回-1，则递归终止，阻断递归，表示不是平衡二叉树

  • 递归方法的功能：获取当前节点的树的高度

Python 版本代码如下： 
class Solution:
    # 计算root节点的高度
    def high(self,root):
        if root == None:
            return 0
        left = self.high(root.left)
        right = self.high(root.right)
        ans = max(left,right)+1
        return ans

    def IsBalanced_Solution(self, pRoot):
        if pRoot == None:
            return True
        # 提前阻断，可行性剪枝
        if not self.IsBalanced_Solution(pRoot.left):
            return False
        if not self.IsBalanced_Solution(pRoot.right):
            return False
        highleft = self.high(pRoot.left)
        highright = self.high(pRoot.right)
        isbalance = highleft - highright
        # 当前节点高度差
        if isbalance > 1&nbs***bsp;isbalance < -1:
            return False
        return True
        # write code here
复杂度分析：

时间复杂度O(N)：递归最差情况下（树退化为链表时），需要使用 O(N) 的栈空间。
空间复杂度O(N)：递归需要使用额外的树节点数量的堆栈空间

总结：解决树的问题时，不仅需要处理特殊情况，还需要注意栈溢出，以及不要陷入递归的逻辑当中
参考资料：
https://blog.nowcoder.net/n/86d140814e39480388326aca3eae4fc6?f=comment