检查一个二叉树是否是平衡二叉树leecode111

需要注意的是从底部往上遍历可以减少重复计算。

package main

//Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
/*leecode111
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。*/
func isBalanced(root *TreeNode) bool {
    return getTreeHeight(root) > -1
}

func getTreeHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := getTreeHeight(root.Left)
    rightHeight := getTreeHeight(root.Right)
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
        return -1
    }
    return max(leftHeight, rightHeight) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func abs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}