剑指 Offer 55 - II. 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

  1. class Solution:
  2.     def depth(self, node):
  3.         if not node:
  4.             return 0
  5.         return max(self.depth(node.left),self.depth(node.right))+1
  7.     def isBalanced(self, root: TreeNode) -> bool:
  8.         if not root:
  9.             return True
  10.         return abs(self.depth(root.left)-self.depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

后序遍历 + 剪枝 （从底至顶）

  1. class Solution:
  2.     def isBalanced(self, root: TreeNode) -> bool:
  3.         def recur(root):
  4.             if not root: return 0
  5.             left = recur(root.left)
  6.             if left == -1: return -1
  7.             right = recur(root.right)
  8.             if right == -1: return -1
  9.             return max(left, right) + 1 if abs(left - right) <= 1 else -1
  11.         return recur(root) != -1
  13. 作者：jyd
  14. 链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/
  15. 来源：力扣（LeetCode）
  16. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。