📑 题目：110. 平衡二叉树

🚀 本题 LeetCode 传送门

题目大意

判断一棵树是不是平衡二叉树。平衡二叉树的定义是：树中每个节点都满足左右两个子树的高度差 <= 1 的这个条件。

解题思路

根据定义判断即可，计算树的高度是第 104 题。

代码

  1. package leetcode
  3. /**
  4.  * Definition for a binary tree node.
  5.  * type TreeNode struct {
  6.  *     Val int
  7.  *     Left *TreeNode
  8.  *     Right *TreeNode
  9.  * }
  10.  */
  11. func isBalanced(root *TreeNode) bool {
  12.  if root == nil {
  13.   return true
  14.  }
  15.  leftHight := depth(root.Left)
  16.  rightHight := depth(root.Right)
  17.  return abs(leftHight-rightHight) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
  18. }
  20. func depth(root *TreeNode) int {
  21.  if root == nil {
  22.   return 0
  23.  }
  24.  return max(depth(root.Left), depth(root.Right)) + 1
  25. }