面试真题

结论：最近公共祖先（LCA）可用递归后序查找或哈希父节点法求解。核心要点：递归法：若根空或根等于p/q返回根；递归左左、右右；若左右均非空则当前根是LCA，否则返回非空的哪边。哈希法：DFS遍历时用哈希表记录每个节点的父节点；从p向上追溯至根存入集合，再从q向上找第一个出现在集合中的节点即为LCA。原理：递归利用子树覆盖关系，找到分叉点；哈希以O(n)空间换O(h)查询，适合多次询问。时间递归O(n)，哈希预处理O(n)查询O(h)。示例：树中p、q分属左右子树时根为其LCA。