coding-tree-search-bst-target简单免费版2000ms未尝试

在二叉搜索树中查找目标值

Search a Binary Search Tree for a Target

开始编码

题目类型

算法 · Graph 算法 · Tree 量化 · Pricing 量化 · Statistics 适配身份 · Quant Developer

题目描述样例编码区结果

在一棵二叉搜索树（BST）中查找 value 等于 target 的节点，返回以该节点为根的整棵子树；如果 target 不在树中则返回 None。这就是 LeetCode 700 的 dict 形式。

利用 BST 不变量，每一步把搜索空间砍半。把 target 与 node["value"] 比较：

相等：命中，返回 node；
较小：递归进 node["left"]（右边的所有值都太大）；
较大：递归进 node["right"]（左边的所有值都太小）。

请实现 solution(tree: dict | None, target: int) -> dict | None。tree 用嵌套字典编码：

空树：None。
节点：{"value": <int>, "left": <subtree>, "right": <subtree>}，其中每个子树本身也要么是节点 dict 要么是 None。

两行递归式：

search(None, target) = None
search(node, target) = node                          if target == node["value"]
                     = search(node["left"], target)  if target < node["value"]
                     = search(node["right"], target) otherwise

最常见的错误是把两边都递归——能跑通但丢了 BST 性质，把 O(h) 的 BST 搜索退化成 O(n) 的普通 DFS。另一个常见错误是返回 node["value"]（只返回整数）或返回布尔，而不是返回整棵子树。看清规格：返回类型是子树 dict（或 None）。

由于深度上界是 1000，而 Python 默认递归上限也是 1000，恰好打满上限的偏斜 BST 会爆栈。请在入口处 sys.setrecursionlimit(2000) 提高上限，或者干脆写成迭代循环。

示例

solution({"value": 5, "left": None, "right": None}, 5) 返回 {"value": 5, "left": None, "right": None}。单节点树，target 命中根节点——返回整棵树（即立刻命中的基底）。

solution({"value": 4, "left": {"value": 2, "left": {"value": 1, "left": None, "right": None}, "right": {"value": 3, "left": None, "right": None}}, "right": {"value": 7, "left": None, "right": None}}, 2) 返回 {"value": 2, "left": {"value": 1, "left": None, "right": None}, "right": {"value": 3, "left": None, "right": None}}。内部节点命中：2 < 4 走左，立刻匹配——返回整棵 3 节点的左子树（约定是「返回子树」，不是只返回 value）。

solution({"value": 4, "left": {"value": 2, "left": None, "right": None}, "right": {"value": 7, "left": None, "right": None}}, 5) 返回 None。未命中：5 > 4 走右到 7，5 < 7 走左进 None，返回 None。BST 搜索一旦走到树外（None）立刻终止。

实战背景

有序数据查找是 quant 交易系统里几乎所有结构的基础原语：每一档订单簿、每个键控缓存、每个评级阶梯、每个限价价位查询，底下都是这套递归。C++ std::map、Python sortedcontainers.SortedDict、JVM TreeMap、kdb+ keyed table，剥开外壳本质上都归结到一棵平衡 BST 的搜索，递归形式跟你正在写的函数一模一样。订单簿里 add_order(price) 在价格级别 BST 上走 O(log L)（L = 不同价位数）；cancel_order(price) 同样这么找；top_of_book() 走最左或最右。曲线定价引擎里，给定 tenor 找折扣因子，是在以 pillar 日期为键的树里查找。风险系统里取 (book, strategy) 键的 WhatIf 情景，也是树搜索。这里的 pricing/probability 标签不是凑数：二叉定价树上的 backward induction 也是一种（不同的）树递归，而对「树上递推」这个 pattern 熟练——基底落在 None、内部节点上做比较、只递归进一边——是读懂、写好任何 quant 定价或执行栈上树算法的入门钥匙。

约束条件

节点数 0 ≤ n_nodes ≤ 10^4。`tree` 要么是 `None`（空树），要么是 dict `{"value": <int>, "left": <subtree>, "right": <subtree>}`，每个子树本身也要么是节点 dict 要么是 `None`。
最大深度 ≤ 1000。纯递归在最大深度边界（偏斜 BST 1000 节点）会触发 Python 默认递归上限（1000）；请在入口处调用 `sys.setrecursionlimit` 抬高到一个安全值（例如 2000），以避免合法的深树打爆栈。
输入保证是合法 BST：每个节点左子树所有值严格小于 `node["value"]`，右子树所有值严格大于。`target` 为整数。
返回值：以匹配节点为根的子树（原节点 dict，不要拷贝），如果 target 不存在则返回 `None`。
评分用对返回 dict 结构的严格相等比较（exact）。

样例

Case 1 · empty tree returns None

输入: [null,5]

期望: null

空树（None）中查找任何 target 都返回 None——这是递归基底。实现必须先判 `node is None`，否则 `node["value"]` 会立即报错。

Case 2 · target equals root returns whole tree

输入: [{"value":4,"left":{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}},"right":{"value":7,"left":{"value":6,"left":null,"right":null},"right":{"value":9,"left":null,"right":null}}},4]

期望: {"value":4,"left":{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}},"right":{"value":7,"left":{"value":6,"left":null,"right":null},"right":{"value":9,"left":null,"right":null}}}

target 等于根节点的 value，立刻命中——返回整棵树本身。这道题钉死「命中节点」的返回约定：返回的是以匹配节点为根的子树（节点 dict），而不是 value、不是路径、不是布尔。

Case 3 · target found at internal node (left subtree)

期望: {"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}

target=2 < root=4，所以进入左子树。左子树根节点的 value 就是 2，命中——返回以 2 为根的整个子树（含 1、3 两个孩子）。这道题验证「返回子树」而不是「只返回该节点的 value」或「只返回该节点本身去掉孩子」。

Case 4 · target found at leaf

期望: {"value":1,"left":null,"right":null}

找到一个叶子节点（target=1）：1 < 4 走左，1 < 2 再走左，命中叶子。返回的是叶子节点本身 `{"value": 1, "left": None, "right": None}`。验证递归在叶子层正确返回，而不是把 None 当作命中。

Case 5 · target not present returns None

期望: null

BST 中不存在 target=5：5 > 4 走右，5 < 7 走左到 6，5 < 6 走左到 None，返回 None。这道题钉死「未命中走到 None 子树」时正确返回 None，而不是返回最后访问的节点。

Case 6 · LeetCode 700 canonical: target=2 in [4,2,7,1,3]

输入: [{"value":4,"left":{"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}},"right":{"value":7,"left":null,"right":null}},2]

期望: {"value":2,"left":{"value":1,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}

LeetCode 700 原题示例：BST 是 [4,2,7,1,3]，target=2，应返回以 2 为根的子树 {value:2,left:{1},right:{3}}。这道题对齐题源约定。

Case 7 · left-skewed chain, target deep on left

输入: [{"value":5,"left":{"value":4,"left":{"value":3,"left":{"value":2,"left":{"value":1,"left":null,"right":null},"right":null},"right":null},"right":null},"right":null},3]

期望: {"value":3,"left":{"value":2,"left":{"value":1,"left":null,"right":null},"right":null},"right":null}

左偏链 5→4→3→2→1（每步都向左）。target=3 < 5 走左，3 < 4 再走左，命中。返回以 3 为根的子树（其左孩子是 {2 → 1} 子树）。这道题验证 BST 性质在左偏形态下也能正确二分缩减。

Case 8 · larger BST, target absent on right side

输入: [{"value":10,"left":{"value":5,"left":{"value":3,"left":null,"right":null},"right":{"value":7,"left":null,"right":null}},"right":{"value":15,"left":{"value":12,"left":null,"right":null},"right":{"value":20,"left":null,"right":null}}},13]

期望: null

较大的 BST（根 10），target=13。13 > 10 走右到 15，13 < 15 走左到 12，13 > 12 走右到 None，返回 None。这道题验证：每次比较都正确剪掉一半子树（不会跑到错误的子树里）。

示例

实战背景

约束条件

样例

最近提交