LeetCode-Go 题解：236. 二叉树最近公共祖先（Lowest Common Ancestor of a Binary Tree）的递归解法

LeetCode-Go 题解236. 二叉树最近公共祖先Lowest Common Ancestor of a Binary Tree的递归解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 0236.Lowest-Common-Ancestor-of-a-Binary-Tree 一题的官方题解与 Go 实现展开完整讲解二叉树最近公共祖先LCA的递归求解思路、代码细节、复杂度分析以及仓库内配套的测试验证方法。读完本文你将掌握任意二叉树场景下 LCA 问题的标准递归解法并能直接复用仓库的测试框架验证自己的实现。题目背景与 LCA 定义题目要求给定一棵二叉树找到树中两个指定节点 p 和 q 的最近公共祖先Lowest Common AncestorLCA。根据维基百科对 LCA 的定义在有根树 T 中p 与 q 的最近公共祖先是 T 中同时以 p 和 q 为后代的最低节点其中允许一个节点是其自身的后代。用中文表述就是对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大。题目给出的示例二叉树为层序数组root [3,5,1,6,2,0,8,null,null,7,4]其结构如下3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4两个官方示例Example 1p 5, q 1输出3。节点 5 和节点 1 分别位于根节点 3 的左右子树它们的最近公共祖先是根节点 3。Example 2p 5, q 4输出5。节点 4 是节点 5 的后代根据节点可以是其自身后代的 LCA 定义节点 5 本身即是 p、q 的最近公共祖先。题目附带两条重要约束树中所有节点的值互不相同p 和 q 是不同的节点且两个值都一定存在于二叉树中。这两条约束直接保证了递归解法中通过指针相等而非值相等判断命中节点的正确性。递归解法自底向上寻找分叉点原题解指出这是一道非常经典的题目核心是考察递归。递归的思路可以概括为自底向上返回命中结果左右都命中时当前节点即为 LCA。对于当前节点 root递归函数lowestCommonAncestor236(root, p, q)的语义是返回以 root 为根的子树中p 与 q 的最近公共祖先若该子树中只包含 p 或 q 之一则返回该节点若二者都不在子树中则返回 nil。具体地每层递归需要回答三个问题当前节点是否命中若root nil子树为空或root p、root q当前节点就是目标节点直接返回 root。这里root q || root p的判断正是节点可以是其自身后代的体现——一旦在某一侧子树中先找到 p 或 q就无需继续向下递归。左右子树分别返回什么分别对左子树和右子树递归调用得到left与right。根据两侧结果汇总left ! nil right ! nilp 和 q 分别位于当前节点的左右两侧子树当前节点就是最近公共祖先返回 root只有left ! nilp、q 都在左子树一侧或其一就是左子树返回的那个节点最近公共祖先在左子树返回 left其余情况返回 right可能右子树有结果也可能两侧都为空返回 nil。这一判断逻辑恰好对应了 LCA 的本质最近公共祖先是 p、q 在树中分道扬镳的那个节点。若两者同侧则继续深入同侧子树若两者分居两侧则当前节点必然是最深的同时包含二者的祖先。仓库中的完整 Go 实现仓库中本题的完整实现位于 236. Lowest Common Ancestor of a Binary Tree.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor236(root, p, q *TreeNode) *TreeNode { if root nil || root q || root p { return root } left : lowestCommonAncestor236(root.Left, p, q) right : lowestCommonAncestor236(root.Right, p, q) if left ! nil { if right ! nil { return root } return left } return right }实现只有十余行但信息密度很高逐点拆解如下类型别名复用type TreeNode structures.TreeNode把仓库公共数据结构包中的 TreeNode 直接复用到本题避免了每个题解目录重复定义树节点。TreeNode 的真实定义在 structures/TreeNode.goVal int、Left *TreeNode、Right *TreeNode。终止条件root nil || root q || root p一行同时处理了子树为空与命中目标两类终止情形。后序遍历形态先递归左右子树再根据结果决定返回值本质上是后序bottom-up遍历保证每个节点只访问一次。空节点安全当 p、q 不在当前子树时递归返回 nil 逐层向上传递最终整体返回 nil本题目约束 p、q 必在树中正常情况下不会走到 nil 结果但代码对这种情况依然安全。复杂度分析时间复杂度O(n)n 为二叉树节点数。最坏情况下需要遍历整棵树例如 p、q 分别位于最深层的两棵子树每个节点恰好被访问一次。空间复杂度O(h)h 为树的高度即递归调用栈的深度。最坏情况下树退化为链表时 h n空间复杂度退化为 O(n)平衡二叉树场景下为 O(log n)。用示例手工推演一遍递归过程以 Example 1p 5, q 1为例跟踪核心路径从 root 3 进入3 不是 nil、也不是 p 或 q于是递归左子树和右子树左子树 root 5命中root p返回节点 5右子树 root 1命中root q返回节点 1回到 root 3 这一层left节点 5与right节点 1均非 nil返回 root 3。再以 Example 2p 5, q 4为例递归到 root 5 时命中 p直接返回节点 5 而不再深入其子树因此根节点 3 一侧只有 left 非 nil、right 为 nil最终返回 left 即节点 5正确体现了节点可以是其自身后代的语义。配套测试仓库如何验证本题仓库为本题编写了完整的单元测试见 236. Lowest Common Ancestor of a Binary Tree_test.go。测试覆盖了 5 组用例层序输入树pq期望输出[]空树--nil[3,5,1,6,2,0,8,null,null,7,4]513[3,5,1,6,2,0,8,null,null,7,4]545[6,2,8,0,4,7,9,null,null,3,5]286[6,2,8,0,4,7,9,null,null,3,5]242其中第 1 组是空树边界期望返回 nil第 2、4 组验证 p、q 分居两侧的常规场景第 3、5 组验证 p 是 q 的祖先或反之时返回祖先节点自身。测试用例的构造方式值得关注它复用了仓库公共结构包提供的两个工具函数均定义于 structures/TreeNode.goInts2TreeNode把 LeetCode 风格的层序数组用structures.NULL表示空节点按层序用队列构建成二叉树。其中NULL -1 63是仓库约定的空节点哨兵值。GetTargetNode在构建好的树中按值查找目标节点返回节点指针供测试用例作为 p、q 参数传入。测试的核心断言是got.Val ! a.one[0]即比较返回节点的值与期望值空树用例则断言返回nil。若需本地运行验证可在仓库根目录执行测试go test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/仓库根目录的 go.mod 通过replace github.com/halfrost/LeetCode-Go/structures ./structures把 structures 包指向本地目录因此无需额外拉取依赖即可直接运行上述测试。对比延伸0235 二叉搜索树版本的 LCA本题0236针对的是任意二叉树只能依靠指针相等与递归遍历求解。仓库中还有一道姊妹题 0235. Lowest Common Ancestor of a Binary Search Tree其实现见 235. Lowest Common Ancestor of a Binary Search Tree.go充分利用了二叉搜索树左小右大的性质func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if p nil || q nil || root nil { return nil } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Left, p, q) } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Right, p, q) } return root }两版解法的本质区别0235BST 版通过比较节点值大小决定只向一侧子树递归平均复杂度 O(log n)是二分思想的直接体现0236普通二叉树版无法利用值序信息必须同时探测左右两棵子树最坏 O(n)是分治 后序汇总思想的典型应用。值得注意的细节是0236 版用root p || root q的指针相等判断命中因为题目保证值唯一、指针可判等而 0235 版用p.Val root.Val的值比较引导搜索方向两者正好展示了 LCA 问题在两种树结构下的不同解题范式。总结二叉树最近公共祖先LCA是面试与算法竞赛中的高频经典题。从 LeetCode-Go 仓库的本题解可以提炼出三条核心经验递归语义要清晰明确返回什么子树内 p、q 的 LCA或命中的单个节点或 nil代码自然水到渠成后序汇总定答案左右子树都命中时当前节点即答案这是最近公共祖先 p、q 分叉点这一本质的直接实现边界与自指语义root p || root q提前返回天然支持节点可以是自身后代的 LCA 定义。如需进一步实践可在仓库根目录运行go test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/复现本文全部用例并结合 structures/TreeNode.go 中的树构建工具自行构造更多测试场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考