110. Balance Binary Tree

题目

给定一柯二叉树，判断是否高度平衡。

解析

一棵高度平衡的二叉树，其每个节点的左右子树高度差小于等于1。
要判断一个二叉树是否高度平衡，需要满足两个条件

1. 左右子树是高度平衡二叉树
2. 左右子树相差不超过1
   即
   f(node) = f(node.Left) && f(node.Right) && |len(node.Left) - len(node.right) | <= 1

要完成这个等式，递归函数还应该返回子树的高度。函数原型为
f(node) int, bool

伪代码

left,isl := f(node.left)
right, isr := f(node.right)
if isl || isr || |left-rigth| > 1
  return 0, false
return max(left,right)+1, true

代码

func isBalanced(root *TreeNode) bool {
    _, is := count(root)
    return is
}

func count(node *TreeNode) (int,bool) {
    if node == nil {
        return 0,true
    }
    left, isl := count(node.Left)
    right, isr := count(node.Right)
    
    if isl && isr && left - right >= -1 && left-right <= 1 {
        return max(left, right)+1, true
    }
    return 0, false
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}