給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節點?的左右兩個子樹的高度差的絕對值不超過1。

示例 1:

給定二叉樹 [3,9,20,null,null,15,7]

3/ \9 20/ \15 7

返回 true 。

示例 2:

給定二叉樹 [1,2,2,3,3,null,null,4,4]

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

返回?false 。

?

遞歸

定義函數 $\text{height}$，用于計算二叉樹中的任意一個節點 $p$ 的高度：

Code

def isBalanced(self, root: TreeNode) -> bool:def dfs(node: TreeNode):if not node:return 0leftDepth = dfs(node.left)rightDepth = dfs(node.right)if abs(leftDepth - rightDepth) > 1:nonlocal flagflag = Falsereturn max(leftDepth, rightDepth) + 1flag = Truedfs(root)return flag

總結

以上是生活随笔為你收集整理的110. Balanced Binary Tree 平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。