🌵110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/
js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
function isBalanced(root) {
if (!root) {
return true
}
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
isBalanced(root.left) && isBalanced(root.right)
}
function maxDepth(root) {
if (!root) {
return 0
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}py
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return abs(self.maxDepth(root.left) - self.maxDepth(root.right)) <= 1 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
def maxDepth(self, root):
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))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
}
ld := maxDepth(root.Left)
rd := maxDepth(root.Right)
return ((ld+1 == rd) || (ld-1 == rd) || ld == rd) &&
isBalanced(root.Left) &&
isBalanced(root.Right)
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
ld := maxDepth(root.Left)
rd := maxDepth(root.Right)
if ld >= rd {
return ld + 1
}
return rd + 1
}