方法一:

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  9. class Solution:
  10.     def checkHeight(self, root:TreeNode):
  11.         if root is None:
  12.             return 0
  13.         else:
  14.             return 1 + max(self.checkHeight(root.left), self.checkHeight(root.right))
  16.     def isBalanced(self, root: TreeNode) -> bool:
  17.         # base case
  18.         if TreeNode is None:
  19.             return True
  20.         h1 = self.checkHeight(root.left)
  21.         h2 = self.checkHeight(root.right)
  22.         if abs(h1 - h2) > 1:
  23.             return False
  24.         else:
  25.             return self.isBalanced(root.left) and self.isBalanced(root.right)

思路

  • 自定向下遍历结点， 计算该节点左右child高度差

    存在的问题

  • isBalanced 是自顶向下的 pre-order , checkHeight 是 post-order , 存在结点高度重复计算的问题

方法二

  2. # Definition for a binary tree node.
  3. class TreeNode:
  4.     def __init__(self, x):
  5.         self.val = x
  6.         self.left = None
  7.         self.right = None
  12. class Solution:
  13.     def checkHeight(self, root: TreeNode):
  14.         # base case
  15.         if root is None:
  16.             return 0
  18.         h1 = self.checkHeight(root.left)
  19.         h2 = self.checkHeight(root.right)
  21.         if h1 == -1 or h2 == -1 or abs(h1 - h2) > 1:
  22.             return -1
  24.         return 1 + max(h1, h2)
  26.     def isBalanced(self, root: TreeNode) -> bool:
  27.         # base case
  28.         return True if self.checkHeight(root) > 0 else False

思路

  • 在计算高度的时候， 已经计算了平衡的信息， 于是将 isBlanced 的先序改成后序， 并合在高度计算过程中。