110. Balanced Binary Tree.md

110. Balanced Binary Tree (Easy)

[tag] DFS

• divide and conquer
• when doing divide and conquer, thinking about return value of DFS, no need for global variables.

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return (True, 0)
            left_ret = dfs(node.left)
            right_ret = dfs(node.right)
            if left_ret[0] and right_ret[0]:
                diff = abs(left_ret[1] - right_ret[1])
                if diff <= 1:
                    return (True, max(left_ret[1], right_ret[1]) + 1)
            
            return (False, -1)
        
        ans = dfs(root)
        return ans[0]