110. Balanced Binary Tree

Leetcode: https://leetcode.com/problems/balanced-binary-tree/

基于tree 的状态检查，常规思路是往上传递 if balanced 这个bool，当前节点的状态取决于：

1. 它两个子树的高度差

2. 它两个子树的状态

节约一点点运算的写法是，一旦检测到not balanced ，就可以不用再继续计算高度了，一路把False 状态传递到根即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.depth(root)[1]
    
    def depth(self, node):
        if not node: return (0, True)
        d_l, b_l = self.depth(node.left)
        d_r, b_r = self.depth(node.right)
        d_curr = max(d_l, d_r) + 1
        b_curr = bool(b_l and b_r) if abs(d_l-d_r) <= 1 else False
        return (d_curr, b_curr)