06 - 二叉树与递归分治¶

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_depth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

from math import inf

def is_valid_bst(root: TreeNode) -> bool:
    def dfs(node):
        if not node:
            return True, inf, -inf
        ok_l, min_l, max_l = dfs(node.left)
        ok_r, min_r, max_r = dfs(node.right)
        ok = ok_l and ok_r and max_l < node.val < min_r
        return ok, min(min_l, node.val), max(max_r, node.val)
    return dfs(root)[0]