leetcood学习笔记-110-平衡二叉树
---恢复内容开始---
题目描述:
方法一:
class Solution(object): def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True if abs(self.countfloor(root.left)-self.countfloor(root.right))>1: return False else: return self.isBalanced(root.left) and self.isBalanced(root.right) def countfloor(self,root): if not root: return 0 else: return max(self.countfloor(root.left),self.countfloor(root.right))+1
法二;效率高
class Solution(object): is_stop = False # 为了加快计算速度, 标志是否已经有结果了 def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ def get_depth_and_balance(root): if self.is_stop: # 已经是非平衡二叉树, 就不需要再计算 return 0, False if not root: return 0, True if not root.left and not root.right: return 1, True ldep, l_is_balanced = get_depth_and_balance(root.left) rdep, r_is_balanced = get_depth_and_balance(root.right) depth = max(ldep, rdep) + 1 is_balanced = abs(ldep- rdep) <= 1 and l_is_balanced and r_is_balanced if not is_balanced: self.is_stop = True return depth, is_balanced depth, is_balanced = get_depth_and_balance(root) return is_balanced