给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
python
# 0110.平衡二叉树
class Solution:
# 递归法
def isBalanced(self, root: TreeNode) -> bool:
return True if self.getDepth(root) != -1 else False
def getDepth(self, node):
if not node:
return 0
leftDepth = self.getDepth(node.left)
# -1->左子树已经不是二叉平衡树
if leftDepth == -1:
return -1
rightDepth = self.getDepth(node.right)
# -1->右子树已经不是二叉平衡树
if rightDepth == -1:
return -1
return -1 if abs(leftDepth - rightDepth) > 1 else 1 + max(leftDepth, rightDepth)
def isBalanced2(self, root: TreeNode) -> bool:
if not root:
return True
stack = []
stack.append(root)
while stack:
node = stack.pop()
if abs(self.getDepth2(node.left) - self.getDepth2(node.right)) > 1:
return False
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return True
def getDepth2(self, cur):
stack = []
if cur:
stack.append(cur)
depth = 0
result = 0
while stack:
node = stack.pop()
if node:
stack.append(node) # 中
stack.append(None)
depth += 1
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
else: # 往上回溯
node = stack.pop()
depth -= 1
result = max(result, depth)
return result
goalng
package binaryTree
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
if !isBalanced(root.Left) || !isBalanced(root.Right) {
return false
}
leftH := maxdepth(root.Left) + 1
rightH := maxdepth(root.Right) + 1
if abs(leftH-rightH) > 1 {
return false
}
return true
}
func maxdepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxdepth(root.Left), maxdepth(root.Right)) + 1
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}