二叉树指定值节点最短深度查找的实现优化与类型标注问题

对于返回值可能为整数也可能为None的情况，可使用typing.Optional[int]作为返回类型标注，以下是修正了原代码笔误（原代码内部误调用self.find_node，应为self.find_depth_of_val）及逻辑漏洞（单边子树找到目标时漏加深度增量1）后的标注版实现：

from typing import Optional

# 二叉树节点类型定义（提前声明）
class TreeNode:
    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
        self.val = val
        self.left = left
        self.right = right

class TreeHandler:
    def find_depth_of_val(self, root: Optional[TreeNode], val: int) -> Optional[int]:
        if not root:
            return None
        if root.val == val:
            return 0
        right_depth = self.find_depth_of_val(root.right, val)
        left_depth = self.find_depth_of_val(root.left, val)
        # 单边无结果的情况直接返回另一侧结果+1
        if right_depth is None:
            return left_depth + 1 if left_depth is not None else None
        if left_depth is None:
            return right_depth + 1
        # 两侧都有结果取最小值+1
        return 1 + min(right_depth, left_depth)

内置无穷大替代魔数 #

无需自定义大数值魔数，使用Python内置的float('inf')（无穷大）作为空路径的返回值，天然大于所有合法深度值，不会出现树深超过魔数的边界问题，代码逻辑和初始版本保持一致，更为简洁：

from typing import Optional, Union

class TreeHandler:
    def find_depth_of_val(self, root: Optional[TreeNode], val: int) -> Union[int, float]:
        if not root:
            return float('inf')
        if root.val == val:
            return 0
        return 1 + min(
            self.find_depth_of_val(root.right, val),
            self.find_depth_of_val(root.left, val)
        )

调用时只需判断返回值是否等于float('inf')，即可确认是否找到目标节点。

BFS迭代实现（更优性能） #

找最小深度的场景下，广度优先搜索（按层遍历）效率更高：第一次匹配到目标值时的层数就是最小深度，无需遍历整棵树，同时也不存在递归栈溢出的风险，适合深度较大的二叉树：

from typing import Optional
from collections import deque

class TreeHandler:
    def find_depth_of_val(self, root: Optional[TreeNode], val: int) -> Optional[int]:
        if not root:
            return None
        # 队列存储(当前节点, 当前深度)
        queue = deque([(root, 0)])
        while queue:
            current_node, depth = queue.popleft()
            if current_node.val == val:
                return depth
            if current_node.left:
                queue.append((current_node.left, depth + 1))
            if current_node.right:
                queue.append((current_node.right, depth + 1))
        # 遍历完全树未找到目标
        return None

内容的提问来源于stack exchange，提问作者amai