## Tree - 110. Balanced Binary Tree

Published on with 0 views and 0 comments

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree `[3,9,20,null,null,15,7]`:

``````    3
/ \
9  20
/  \
15   7
``````

Return true.

Example 2:

Given the following tree `[1,2,2,3,3,null,null,4,4]`:

``````       1
/ \
2   2
/ \
3   3
/ \
4   4

``````

Return false.

go：

``````/**

* Definition for a binary tree node.

* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}

left := depth(root.Left)
right := depth(root.Right)

return abs(left, right) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func depth(node *TreeNode) int {
if node == nil {
return 0
}
return max(depth(node.Left), depth(node.Right)) + 1
}

func abs(i, j int) int {
if i > j {
return i - j
}
return j - i
}

func max(i, j int) int {
if i > j {
return i
}
return j
}
``````