本文共 1494 字，大约阅读时间需要 4 分钟。

此题为 的拓展，建议先做上一题。

该方法基于以下性质推出： 此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1

【思路】对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

【算法流程】

• recur(root) 函数：

  • 返回值：
  1. 当节点root 左 / 右子树的深度差 ≤1 ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值 +1 （max(left, right) + 1）；
  2. 当节点root 左 / 右子树的深度差 >1 ：则返回 −1 ，代表 此子树不是平衡树 。
  • 终止条件：
  1. 当 root 为空：说明越过叶节点，因此返回高度 00 ；
  2. 当左（右）子树深度为 -1−1 ：代表此树的 左（右）子树 不是平衡树，因此剪枝，直接返回 -1−1 ；

• isBalanced(root) 函数：

返回值： 若 recur(root) != -1 ，则说明此树平衡，返回 truetrue ； 否则返回 falsefalse 。

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def isBalanced(self, root: TreeNode) -> bool:        def recur(root):            if not root:                return 0            # 判左是否为平衡二叉树？            left = recur(root.left)            if left == -1:                return -1                        # 判右是否为平衡二叉树？            right = recur(root.right)            if right == -1:                return -1            # 左右子树只差大于1，也不是为平衡二叉树            # 可简化为三目运算：            # return max(left, right) + 1 if abs(left - right) <= 1 else -1            if abs(left-right)<=1:                return max(left,right)+1            else:                return -1        return recur(root)!=-1

复杂度分析：

• 时间复杂度 O(N)： NN 为树的节点数；最差情况下，需要递归遍历树的所有节点。
• 空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N)O(N) 的栈空间。

https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9hscjv/

转载地址：http://xyjii.baihongyu.com/