引言 (Introduction)
在掌握了基础遍历后，我们需要面对具有特定逻辑约束的树结构——二叉搜索树（BST），以及涉及节点间拓扑关系的路径问题。BST 通过引入排序约束，将查找的平均时间复杂度降到了 $O(\log N)$。这些算法不仅考察代码实现能力，更考验对递归边界、搜索空间以及回溯思想的把握。
本文是本系列第二篇，所有的代码实现均基于以下标准节点定义：
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
1. 二叉搜索树 (BST) 的验证与特性
BST 的核心特性是：对于任意节点，其左子树中的所有节点值均严格小于它，右子树中的所有节点值均严格大于它。并且，它的左右子树也必须分别是二叉搜索树。
1.1 验证二叉搜索树 (Validate BST)
初学者常犯的错误是仅仅比较当前节点与其左右孩子的值。这样会导致遗漏“右子树的左孩子必须大于根节点”这一隐式约束。因此，我们需要在递归时不断传递并收窄允许的取值区间 (low, high)。
def is_valid_bst(root: Optional[TreeNode]) -> bool:
"""验证是否为有效的二叉搜索树"""
def validate(node: Optional[TreeNode], low: float = -float('inf'), high: float = float('inf')) -> bool:
if not node:
return True
# 节点值必须在严格的开区间 (low, high) 内
if not (low < node.val < high):
return False
# 递归验证左子树：上限更新为当前节点的值
# 递归验证右子树：下限更新为当前节点的值
return validate(node.left, low, node.val) and \
validate(node.right, node.val, high)
return validate(root)
复杂度分析：时间复杂度 $O(N)$，空间复杂度 $O(H)$。
2. 最近公共祖先 (LCA)
寻找两个节点 $p$ 和 $q$ 的最近公共祖先（Lowest Common Ancestor）是树论中的经典问题。所谓 LCA，即在树中深度最大的（最底层的）共同祖先。
2.1 普通二叉树的 LCA 实现
如果在普通二叉树中寻找，我们采取自底向上的后序遍历思想：如果一个节点的左子树发现了一个目标节点，右子树发现了另一个目标节点，那么这个节点就是 LCA。如果全在一边，那最先遇到的那个节点就是 LCA。
def lowest_common_ancestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'Optional[TreeNode]':
"""求普通二叉树的最近公共祖先"""
# 递归终止条件：遇到空节点，或者碰到了目标节点 p 或 q
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)
# 如果左右子树各找到了一个，说明当前节点是它们的分界点，即 LCA
if left and right:
return root
# 如果只在左边找到，返回左边的结果；反之亦然
return left or right
3. 路径求和问题 (Path Sum)
路径问题通常需要我们从根节点一路向下探索，这本质上是一个**回溯（Backtracking）**的过程，尽管在简单的树结构中回溯状态可以通过传值隐式完成。
3.1 路径总和 I
题目描述：判断树中是否存在一条从根节点到叶子节点的路径，其所有节点值相加等于目标和 targetSum。
def has_path_sum(root: Optional[TreeNode], targetSum: int) -> bool:
"""判断是否存在根到叶子的路径总和"""
if not root:
return False
# 如果是叶子节点，检查剩余的 targetSum 是否刚好等于当前节点的值
if not root.left and not root.right:
return targetSum == root.val
# 递归查找左右子树，目标和减去当前节点的值
# 只要有一条路径满足即可（逻辑或）
return has_path_sum(root.left, targetSum - root.val) or \
has_path_sum(root.right, targetSum - root.val)
4. 构造与展开
4.1 二叉树展开为链表 (Flatten Binary Tree to Linked List)
题目描述：将二叉树原地展开为单链表，展开后的单链表应该与二叉树的先序遍历顺序相同，且所有节点只有 right 指针，left 指针全为 None。
解题逻辑（空间优化版 $O(1)$）：对于当前节点，如果它有左子树，我们需要把它的右子树接到它左子树的最右侧节点（即先序遍历中左子树访问的最后一个节点）的右边。然后把整个左子树移到右边去。
def flatten(root: Optional[TreeNode]) -> None:
"""将二叉树原地展开为链表"""
curr = root
while curr:
if curr.left:
# 1. 找到左子树的最右侧节点（前驱节点）
predecessor = curr.left
while predecessor.right:
predecessor = predecessor.right
# 2. 将原本的右子树接到 predecessor 的右边
predecessor.right = curr.right
# 3. 将整个左子树移到当前节点的右侧，并将左侧置空
curr.right = curr.left
curr.left = None
# 4. 继续处理下一个节点
curr = curr.right
结论 (Conclusion)
BST 的严格有序性和路径问题的递归状态传递是二叉树算法的中坚力量。理解这些算法的关键在于：明确递归函数在每一层需要的入参边界以及返回值代表的物理意义。下一篇我们将挑战二叉树的极致空间优化与复杂树形持久化问题。