444_二叉树面试题精选¶

前序：根 → 左 → 右  （先处理自己）
中序：左 → 根 → 右  （对BST就是升序）
后序：左 → 右 → 根  （先处理子节点，最后处理自己）

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

def max_depth(root) -> int:
    """
    递归思路：当前节点的深度 = 1 + max(左子树深度, 右子树深度)
    base case：空节点深度为0
    """
    if not root:                           # 空节点，深度为0
        return 0

    left_depth = max_depth(root.left)      # 左子树最大深度
    right_depth = max_depth(root.right)    # 右子树最大深度

    return 1 + max(left_depth, right_depth)  # 当前节点深度=子树最大+1

# BFS 迭代法（层序遍历，每层+1）
from collections import deque

def max_depth_bfs(root) -> int:
    if not root:
        return 0

    queue = deque([root])                  # 从根节点开始
    depth = 0

    while queue:
        depth += 1                         # 每处理一层，深度+1
        for _ in range(len(queue)):        # 处理当前层所有节点
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth

def is_valid_bst(root) -> bool:
    """
    思路：递归传入合法范围 [min_val, max_val]
    每个节点的值必须在这个范围内
    往左走时，上界更新为当前值；往右走时，下界更新为当前值
    """
    def validate(node, min_val, max_val):
        if not node:                       # 空节点默认合法
            return True

        # 当前节点值必须严格在 (min_val, max_val) 范围内
        if node.val <= min_val or node.val >= max_val:
            return False

        # 递归左子树：左子树所有值必须 < node.val（更新上界）
        # 递归右子树：右子树所有值必须 > node.val（更新下界）
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))  # 初始范围无穷大

# 中序遍历法：BST中序遍历结果必须是严格递增序列
def is_valid_bst_inorder(root) -> bool:
    prev = float('-inf')                   # 记录上一个访问的值

    def inorder(node):
        nonlocal prev
        if not node:
            return True

        if not inorder(node.left):         # 先检查左子树
            return False

        if node.val <= prev:               # 当前值必须严格大于前一个
            return False
        prev = node.val                    # 更新前一个值

        return inorder(node.right)         # 再检查右子树

    return inorder(root)

def level_order(root):
    """
    BFS：用队列按层处理
    关键：每层开始时记录队列长度，只处理这么多节点（当前层）
    """
    if not root:
        return []

    result = []                            # 存每层的结果
    queue = deque([root])                  # 初始只有根节点

    while queue:
        level_size = len(queue)            # 当前层的节点数
        level_vals = []                    # 当前层的值

        for _ in range(level_size):        # 只处理当前层
            node = queue.popleft()
            level_vals.append(node.val)

            if node.left:                  # 下一层的节点加入队列
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_vals)          # 当前层处理完毕

    return result

# 测试
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(level_order(root))  # [[3], [9, 20], [15, 7]]

def lowest_common_ancestor(root, p, q):
    """
    后序遍历：先递归左右，再在当前节点做判断
    如果左右各找到一个，则当前节点就是 LCA
    """
    if not root or root == p or root == q: # 找到目标节点或到底
        return root

    left = lowest_common_ancestor(root.left, p, q)   # 左子树找
    right = lowest_common_ancestor(root.right, p, q)  # 右子树找

    if left and right:                     # 左右各找到一个，当前节点是LCA
        return root
    return left if left else right         # 只有一侧找到，返回那侧

# 前序遍历（递归）
def preorder(node):
    if not node: return
    print(node.val)    # 处理当前
    preorder(node.left)
    preorder(node.right)

# 中序遍历（递归）
def inorder(node):
    if not node: return
    inorder(node.left)
    print(node.val)    # 处理当前（BST中是升序）
    inorder(node.right)

# 后序遍历（递归）
def postorder(node):
    if not node: return
    postorder(node.left)
    postorder(node.right)
    print(node.val)    # 处理当前（最后处理自己）

# 层序遍历（BFS，必背）
queue = deque([root])
while queue:
    size = len(queue)
    for _ in range(size):
        node = queue.popleft()
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)