题目分析：
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:给定二叉树 [3,9,20,null,null,15,7] 返回 true 。
示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 返回 false 。
解题思路：
思路一： 我们在【LeetCode】104. Maximum Depth of Binary Tree写过计算二叉树深度的代码，我们可以使用那一题的代码来计算每个节点左右的深度，然后做差判断。
获取节点深度函数（与【LeetCode】104. Maximum Depth of Binary Tree递归代码相同） def getDepth(self, root: TreeNode) -> int: if not root: return 0 return 1 + max(self.getDepth(root.left), self.getDepth(root.right)) 判断根节点左右子树深度差是否超过1，大于1就返回错误 if abs(self.getDepth(root.left) - self.getDepth(root.right)) > 1: return False 递归根节点的左右子树 return self.isBalanced(root.left) and self.isBalanced(root.right)思路二： 思路一简单易懂，效率偏低的主要原因是，如下图，首先会递归计算9与20的深度，然后又会递归计算已经算过的15和7的深度，也就是说它计算节点深度会把所有根节点全计算一遍。 改进思路一
我们每次计算节点深度同时判断是否为平衡树，是的话就返回深度给上一层，否则返回-1 return (1 + max(left_depth, right_depth)) if abs(left_depth - right_depth) <= 1 else -1 然后如果节点值为-1，代表该节点已经不为平衡树，我们就一直向上层返回-1 left_depth = self.dfs(root.left) if left_depth == -1: return -1 right_depth = self.dfs(root.right) if right_depth == -1: return -1 最外层函数接收到返回-1，就知道不是平衡树了，这样仅深度递归一次就解决了问题（有些节点没有计算是小于等于一次的） return self.dfs(root) != -1提交代码1：（简单递归，Runtime: 76 ms, faster than 39.60% ）
class Solution: def isBalanced(self, root: TreeNode) -> bool: if not root: return True if abs(self.getDepth(root.left) - self.getDepth(root.right)) > 1: return False return self.isBalanced(root.left) and self.isBalanced(root.right) def getDepth(self, root: TreeNode) -> int: if not root: return 0 return 1 + max(self.getDepth(root.left), self.getDepth(root.right))提交代码2：（同时计算深度与平衡树的递归，时间复杂度O(N)，Runtime: 48 ms, faster than 99.67% ）
class Solution: def isBalanced(self, root: TreeNode) -> bool: return self.dfs(root) != -1 def dfs(self, root: TreeNode) -> int: if not root: return True left_depth = self.dfs(root.left) if left_depth == -1: return -1 right_depth = self.dfs(root.right) if right_depth == -1: return -1 return (1 + max(left_depth, right_depth)) if abs(left_depth - right_depth) <= 1 else -1参考博客
