1, 题目

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:

  1. 给定二叉树 [3,9,20,null,null,15,7]
  2.    3
  3.   / \
  4.  9  20
  5.    /  \
  6.   15   7
  7. 返回 true 。

示例 2:

  1. 给定二叉树 [1,2,2,3,3,null,null,4,4]
  2.       1
  3.      / \
  4.     2   2
  5.    / \
  6.   3   3
  7.  / \
  8. 4   4
  9. 返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. #scala
  2. object Solution {
  3.     def isBalanced(root: TreeNode): Boolean = {
  4.         if (root == null) {
  5.             return true
  6.         }
  7.         if (isBalanced(root.left)) {
  8.             if (isBalanced(root.right)) {
  9.                 (depth(root.left) - depth(root.right)).abs <= 1
  10.             } else {
  11.                 false
  12.             }
  13.         } else {
  14.             false
  15.         }
  16.     }
  18.     def depth(root: TreeNode): Int = {
  19.         if (root == null) {
  20.             0
  21.         } else {
  22.             depth(root.left).max(depth(root.right)) + 1
  23.         }
  24.     }
  25. }
  1. #python
  2. class Solution:
  3.     def isBalanced(self, root: TreeNode) -> bool:
  4.         if root:
  5.             if self.isBalanced(root.left):
  6.                 if self.isBalanced(root.right):
  7.                     return abs(self.depth(root.left) - self.depth(root.right)) <= 1
  8.                 else:
  9.                     return False
  10.             else:
  11.                 return False
  12.         else:
  13.             return True
  15.     def depth(self, root: TreeNode) -> int:
  16.         if root:
  17.             return max(self.depth(root.left), self.depth(root.right)) + 1
  18.         else:
  19.             return 0