LCA

副标题 / 摘要 LeetCode 236 的真正难点不是“记住 LCA 模板”，而是先定义清楚：递归函数到底要向父节点返回什么信息。只要这个返回值语义稳定，整题就会自然落成一段非常短但非常强的后序递归。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、LCA、DFS、后序遍历 SEO 关键词：Lowest Common Ancestor of a Binary Tree, 二叉树的最近公共祖先, LCA, 后序遍历, DFS, LeetCode 236 元描述：系统讲透 LeetCode 236 的后序返回值定义、节点自祖先规则、递归推导过程、工程迁移和多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树，找到该树中两个指定节点 p 和 q 的最近公共祖先。 最近公共祖先（LCA）的定义是： x 同时是 p 和 q 的祖先 在满足上面条件的节点里，x 的深度尽可能大 一个节点也可以是它自己的祖先 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 p, q TreeNode 树中的两个指定节点；示例输入里用它们的唯一值表示 返回 TreeNode p 和 q 的最近公共祖先 示例 1 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3 输入：root = [1,2], p = 1, q = 2 输出：1 提示 树中节点数目在范围 [2, 10^5] 内 -10^9 <= Node.val <= 10^9 所有 Node.val 互不相同 p != q p 和 q 均存在于给定的二叉树中 目标读者 已经会写普通树递归，但一到“最近公共祖先”就容易卡在返回值定义上的学习者 想把后序分治写法固定成稳定模板的开发者 在工程里处理组织树、组件树、目录树共享祖先问题的工程师 背景 / 动机 很多人第一次做 236，会下意识想到： ...