原题链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
解题思路:
- 方法一:递归求出左右子节点的深度,然后对比深度差是否大于1,复杂度较高,会重复计算;
- 方法二:在递归求左右子节点深度的过程中,加入判断,如果某个节点node的左右叶子节点深度差小于1,则返回该node的深度,否则返回-1,一旦某个节点node的左右叶子节点深度差返回-1,则继续向上返回-1,最终返回False。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def maxDepth(root) -> int:
if not root: return 0
return max(maxDepth(root.left), maxDepth(root.right))+1
if not root: return True
return abs(maxDepth(root.left)-maxDepth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def depth(node):
if not node: return 0
left = depth(node.left)
if left == -1: return -1
right = depth(node.right)
if right == -1: return -1
return max(left,right)+1 if abs(left-right)<=1 else -1
return depth(root) != -1