The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104
Solutions
Solution 1: Bottom-Up Recursion
We define a function $height(root)$ to calculate the height of a binary tree, with the following logic:
If the binary tree $root$ is null, return $0$.
Otherwise, recursively calculate the heights of the left and right subtrees, denoted as $l$ and $r$ respectively. If either $l$ or $r$ is $-1$, or the absolute difference between $l$ and $r$ is greater than $1$, then return $-1$. Otherwise, return $max(l, r) + 1$.
Therefore, if the function $height(root)$ returns $-1$, it means the binary tree $root$ is not balanced. Otherwise, it is balanced.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defisBalanced(self,root:Optional[TreeNode])->bool:defheight(root):ifrootisNone:return0l,r=height(root.left),height(root.right)ifl==-1orr==-1orabs(l-r)>1:return-1return1+max(l,r)returnheight(root)>=0
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisBalanced(root*TreeNode)bool{varheightfunc(*TreeNode)intheight=func(root*TreeNode)int{ifroot==nil{return0}l,r:=height(root.Left),height(root.Right)ifl==-1||r==-1||abs(l-r)>1{return-1}ifl>r{return1+l}return1+r}returnheight(root)>=0}funcabs(xint)int{ifx<0{return-x}returnx}