尧图网站建设 
LeetCode-Go 题解 235二叉搜索树的最近公共祖先Lowest Common Ancestor of a BST【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 235 题 Lowest Common Ancestor of a Binary Search Tree二叉搜索树的最近公共祖先展开以 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree 目录下的题解文档、Go 实现与测试用例为核心素材。读完本文你将掌握BST 中最近公共祖先的判定规则、基于值域分岔的递归算法原理与 Go 实现细节、测试数据的构造方式含structures.NULL哨兵约定以及如何在本仓库中独立运行该题的单测与覆盖率检查。一、题目定义BST 中的 LCA给定一棵二叉搜索树BST和树中两个指定节点p、q找出它们的最近公共祖先Lowest Common Ancestor简称 LCA。根据维基百科对 LCA 的定义最近公共祖先定义为树 T 中同时以 p 和 q 为后代的最低节点允许一个节点是它自身的后代。注意这里的特殊性一个节点可以是它自己的祖先因此当p或q恰好是对方祖先时祖先节点本身即为答案。本题给定二叉搜索树层序表示root [6,2,8,0,4,7,9,null,null,3,5]对应的树形结构为根节点 6左子树根 2其左子 0、右子 4右子树根 8其左子 7、右子 9节点 4 下挂 3 与 5。示例 1Input: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.节点 2 位于根节点 6 的左子树节点 8 位于根节点 6 的右子树二者分处两侧唯一的公共祖先便是根节点 6。示例 2Input: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.节点 2 与节点 4 同在左子树且节点 2 是节点 4 的祖先。按节点可以是自身后代的规则答案为 2。题目约束Note树中所有节点的值唯一All of the nodes values will be uniquep和q互不相同且两个值都一定存在于该 BST 中p and q are different and both values will exist in the BST。这两条约束保证值可以安全地作为节点的唯一标识且无需处理目标节点不存在的边界分支。二、核心思路利用 BST 值域特性做分岔判定普通二叉树求 LCA 需要自底向上递归收集祖先链而本题文档明确指出在二叉搜索树中求两个节点的最近公共祖先由于二叉搜索树的特殊性质所以找任意两个节点的最近公共祖先非常简单。二叉搜索树的关键性质是对任意节点root其左子树所有节点值都小于root.Val右子树所有节点值都大于root.Val。因此对于两个目标节点p、q与当前考察节点root之间只存在三种关系判定条件含义动作p.Val root.Val q.Val root.Valp、q 都在root的左子树中递归进入root.Leftp.Val root.Val q.Val root.Valp、q 都在root的右子树中递归进入root.Right其余情况一个小于一个大于或之一等于root.Valp、q 分处两侧或当前节点就是 p/q 本身当前root即为答案第三种情况即分岔点一旦p、q分处当前节点的左右两侧或其中一个就是当前节点那么从根往下继续深入只会走进某一侧子树另一侧的目标将丢失因此当前节点必然是唯一的、深度最大的公共祖先。复杂度分析每一层递归只向单侧子树下降一层高度为h平衡时h log n最坏退化为O(n)因此时间复杂度为O(h)递归栈深度同样为O(h)空间复杂度O(h)全程无额外数据结构。三、Go 实现解析仓库源码逐行拆解本仓库的完整实现位于 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/235. Lowest Common Ancestor of a Binary Search Tree.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode 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 }3.1 节点类型复用函数签名root, p, q *TreeNode直接复用 structures/TreeNode.go 中定义的公共树节点结构// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }并通过类型别名type TreeNode structures.TreeNode引入这正是本仓库大量二叉树题目的统一做法保证所有题目共用同一套树结构与辅助工具函数。3.2 空指针保护if p nil || q nil || root nil { return nil }虽然题目保证p、q一定存在但仓库实现仍保留空指针防护使函数在空树、或传入空节点时安全返回nil也让测试用例可以覆盖空输入分支见下文测试第一组。3.3 递归下降与终止条件两个目标值都小于当前节点 → 公共祖先一定在左子树递归root.Left两个目标值都大于当前节点 → 公共祖先一定在右子树递归root.Right其余情况直接返回root包括p、q分居两侧以及p或q恰好等于当前节点自身即祖先两种情形一并由最后一行覆盖无需额外判断。这段实现的核心美学在于BST 的序关系让是否分岔的判断退化为三次值比较连显式的栈或路径收集都不需要。四、测试用例解读如何用层序数组构造 BST配套测试位于 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/235. Lowest Common Ancestor of a Binary Search Tree_test.go采用本仓库统一的para参数 ans期望答案表驱动风格qs : []question235{ { para235{[]int{}, []int{}, []int{}}, ans235{[]int{}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{2}, []int{8}}, ans235{[]int{6}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{2}, []int{4}}, ans235{[]int{2}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{7}, []int{9}}, ans235{[]int{8}}, }, }测试共覆盖四组场景空输入三棵均为空树期望返回nil验证空指针保护分支示例 1p 2, q 8分居两侧期望 6示例 2p 2, q 4p是q的祖先期望 2验证自身即祖先规则补充用例p 7, q 9同在右子树期望 8验证向右递归分支。4.1 structures.NULL 哨兵约定[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}是层序level-order展开null位置用哨兵值 structures.NULL 表示// NULL 方便添加测试数据 var NULL -1 63由于题目保证节点值唯一且为普通整数NULL取 int64 最小值作为不可能出现的占位符是安全的。测试中通过structures.Ints2TreeNode(p.one)把层序数组构造成树相关实现见 Ints2TreeNode它用队列按层序把ints[i]依次挂到节点的左右子树上遇到NULL则跳过建点与 LeetCode 平台给出的[6,2,8,0,4,7,9,null,null,3,5]输入完全对应。4.2 结果断言got : lowestCommonAncestor(rootOne, rootTwo, rootThr) if len(a.one) 0 { if got ! nil { t.Fatalf(...) } continue } if got nil || got.Val ! a.one[0] { t.Fatalf(input %v: expected %v, got %v, p, a.one[0], got) }空期望对应空断言非空期望则比较返回节点的Val。测试运行时会打印【input】与【output】便于人工核对整棵树的构造与结果。五、在本地运行与验证5.1 运行单题测试仓库根目录的 go.mod 声明module github.com/halfrost/LeetCode-GoGo 1.19并通过replace指令把structures等子模块映射到本地目录。进入仓库根目录后执行go test -v -run Test_Problem235 ./leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/-run Test_Problem235精确匹配测试函数名-v可看到【input】/【output】的逐条打印。5.2 跑全量测试并生成覆盖率仓库提供一键脚本 gotest.sh它对全部leetcode题目执行带覆盖率收集的测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/..../gotest.sh脚本会在仓库根目录生成coverage.txt。本仓库的题解以 100% 测试覆盖率为目标本题四组用例正好覆盖空分支、左递归、右递归与自身祖先四条路径实现与测试一一对应这正是仓库runtime beats 100%之外测试侧的自洽保证。六、延伸对比与 236 题普通二叉树的区别同目录下还有姊妹题 236. Lowest Common Ancestor of a Binary Tree。两道题的区别要点如下维度235本题BST236普通二叉树可利用性质节点值有序可单向递归无序需后序遍历回溯核心判定值域分岔一侧则深入分岔则返回左右子树是否命中 p/q时空复杂度O(h)时间 /O(h)空间O(n)时间 /O(n)空间题目定位借助 BST 性质快速定位考察经典递归回溯范式如果先把 235 的值域分岔思想吃透再对比 236 的通用递归解法就能理解 LCA 问题中数据结构性质决定算法复杂度这一核心观察。七、小结本文完整还原了 LeetCode 235 题的题面、约束与示例并基于 LeetCode-Go 仓库的源码与测试给出逐行级解读递归实现只依赖三次值比较即可定位 BST 中的 LCAstructures.NULL哨兵与Ints2TreeNode完成了 LeetCode 层序输入到 Go 树对象的映射gotest.sh提供了一条命令跑完全部题目并生成覆盖率报告。掌握分岔判定 单侧递归的模式后你可以把它直接迁移到BST 中找第 k 小BST 中找区间和等同类值域导向的题目中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 235：二叉搜索树的最近公共祖先（Lowest Common Ancestor of a BST）
LeetCode-Go 题解 235二叉搜索树的最近公共祖先Lowest Common Ancestor of a BST【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 235 题 Lowest Common Ancestor of a Binary Search Tree二叉搜索树的最近公共祖先展开以 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree 目录下的题解文档、Go 实现与测试用例为核心素材。读完本文你将掌握BST 中最近公共祖先的判定规则、基于值域分岔的递归算法原理与 Go 实现细节、测试数据的构造方式含structures.NULL哨兵约定以及如何在本仓库中独立运行该题的单测与覆盖率检查。一、题目定义BST 中的 LCA给定一棵二叉搜索树BST和树中两个指定节点p、q找出它们的最近公共祖先Lowest Common Ancestor简称 LCA。根据维基百科对 LCA 的定义最近公共祖先定义为树 T 中同时以 p 和 q 为后代的最低节点允许一个节点是它自身的后代。注意这里的特殊性一个节点可以是它自己的祖先因此当p或q恰好是对方祖先时祖先节点本身即为答案。本题给定二叉搜索树层序表示root [6,2,8,0,4,7,9,null,null,3,5]对应的树形结构为根节点 6左子树根 2其左子 0、右子 4右子树根 8其左子 7、右子 9节点 4 下挂 3 与 5。示例 1Input: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.节点 2 位于根节点 6 的左子树节点 8 位于根节点 6 的右子树二者分处两侧唯一的公共祖先便是根节点 6。示例 2Input: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.节点 2 与节点 4 同在左子树且节点 2 是节点 4 的祖先。按节点可以是自身后代的规则答案为 2。题目约束Note树中所有节点的值唯一All of the nodes values will be uniquep和q互不相同且两个值都一定存在于该 BST 中p and q are different and both values will exist in the BST。这两条约束保证值可以安全地作为节点的唯一标识且无需处理目标节点不存在的边界分支。二、核心思路利用 BST 值域特性做分岔判定普通二叉树求 LCA 需要自底向上递归收集祖先链而本题文档明确指出在二叉搜索树中求两个节点的最近公共祖先由于二叉搜索树的特殊性质所以找任意两个节点的最近公共祖先非常简单。二叉搜索树的关键性质是对任意节点root其左子树所有节点值都小于root.Val右子树所有节点值都大于root.Val。因此对于两个目标节点p、q与当前考察节点root之间只存在三种关系判定条件含义动作p.Val root.Val q.Val root.Valp、q 都在root的左子树中递归进入root.Leftp.Val root.Val q.Val root.Valp、q 都在root的右子树中递归进入root.Right其余情况一个小于一个大于或之一等于root.Valp、q 分处两侧或当前节点就是 p/q 本身当前root即为答案第三种情况即分岔点一旦p、q分处当前节点的左右两侧或其中一个就是当前节点那么从根往下继续深入只会走进某一侧子树另一侧的目标将丢失因此当前节点必然是唯一的、深度最大的公共祖先。复杂度分析每一层递归只向单侧子树下降一层高度为h平衡时h log n最坏退化为O(n)因此时间复杂度为O(h)递归栈深度同样为O(h)空间复杂度O(h)全程无额外数据结构。三、Go 实现解析仓库源码逐行拆解本仓库的完整实现位于 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/235. Lowest Common Ancestor of a Binary Search Tree.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode 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 }3.1 节点类型复用函数签名root, p, q *TreeNode直接复用 structures/TreeNode.go 中定义的公共树节点结构// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }并通过类型别名type TreeNode structures.TreeNode引入这正是本仓库大量二叉树题目的统一做法保证所有题目共用同一套树结构与辅助工具函数。3.2 空指针保护if p nil || q nil || root nil { return nil }虽然题目保证p、q一定存在但仓库实现仍保留空指针防护使函数在空树、或传入空节点时安全返回nil也让测试用例可以覆盖空输入分支见下文测试第一组。3.3 递归下降与终止条件两个目标值都小于当前节点 → 公共祖先一定在左子树递归root.Left两个目标值都大于当前节点 → 公共祖先一定在右子树递归root.Right其余情况直接返回root包括p、q分居两侧以及p或q恰好等于当前节点自身即祖先两种情形一并由最后一行覆盖无需额外判断。这段实现的核心美学在于BST 的序关系让是否分岔的判断退化为三次值比较连显式的栈或路径收集都不需要。四、测试用例解读如何用层序数组构造 BST配套测试位于 leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/235. Lowest Common Ancestor of a Binary Search Tree_test.go采用本仓库统一的para参数 ans期望答案表驱动风格qs : []question235{ { para235{[]int{}, []int{}, []int{}}, ans235{[]int{}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{2}, []int{8}}, ans235{[]int{6}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{2}, []int{4}}, ans235{[]int{2}}, }, { para235{[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}, []int{7}, []int{9}}, ans235{[]int{8}}, }, }测试共覆盖四组场景空输入三棵均为空树期望返回nil验证空指针保护分支示例 1p 2, q 8分居两侧期望 6示例 2p 2, q 4p是q的祖先期望 2验证自身即祖先规则补充用例p 7, q 9同在右子树期望 8验证向右递归分支。4.1 structures.NULL 哨兵约定[]int{6, 2, 8, 0, 4, 7, 9, structures.NULL, structures.NULL, 3, 5}是层序level-order展开null位置用哨兵值 structures.NULL 表示// NULL 方便添加测试数据 var NULL -1 63由于题目保证节点值唯一且为普通整数NULL取 int64 最小值作为不可能出现的占位符是安全的。测试中通过structures.Ints2TreeNode(p.one)把层序数组构造成树相关实现见 Ints2TreeNode它用队列按层序把ints[i]依次挂到节点的左右子树上遇到NULL则跳过建点与 LeetCode 平台给出的[6,2,8,0,4,7,9,null,null,3,5]输入完全对应。4.2 结果断言got : lowestCommonAncestor(rootOne, rootTwo, rootThr) if len(a.one) 0 { if got ! nil { t.Fatalf(...) } continue } if got nil || got.Val ! a.one[0] { t.Fatalf(input %v: expected %v, got %v, p, a.one[0], got) }空期望对应空断言非空期望则比较返回节点的Val。测试运行时会打印【input】与【output】便于人工核对整棵树的构造与结果。五、在本地运行与验证5.1 运行单题测试仓库根目录的 go.mod 声明module github.com/halfrost/LeetCode-GoGo 1.19并通过replace指令把structures等子模块映射到本地目录。进入仓库根目录后执行go test -v -run Test_Problem235 ./leetcode/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/-run Test_Problem235精确匹配测试函数名-v可看到【input】/【output】的逐条打印。5.2 跑全量测试并生成覆盖率仓库提供一键脚本 gotest.sh它对全部leetcode题目执行带覆盖率收集的测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/..../gotest.sh脚本会在仓库根目录生成coverage.txt。本仓库的题解以 100% 测试覆盖率为目标本题四组用例正好覆盖空分支、左递归、右递归与自身祖先四条路径实现与测试一一对应这正是仓库runtime beats 100%之外测试侧的自洽保证。六、延伸对比与 236 题普通二叉树的区别同目录下还有姊妹题 236. Lowest Common Ancestor of a Binary Tree。两道题的区别要点如下维度235本题BST236普通二叉树可利用性质节点值有序可单向递归无序需后序遍历回溯核心判定值域分岔一侧则深入分岔则返回左右子树是否命中 p/q时空复杂度O(h)时间 /O(h)空间O(n)时间 /O(n)空间题目定位借助 BST 性质快速定位考察经典递归回溯范式如果先把 235 的值域分岔思想吃透再对比 236 的通用递归解法就能理解 LCA 问题中数据结构性质决定算法复杂度这一核心观察。七、小结本文完整还原了 LeetCode 235 题的题面、约束与示例并基于 LeetCode-Go 仓库的源码与测试给出逐行级解读递归实现只依赖三次值比较即可定位 BST 中的 LCAstructures.NULL哨兵与Ints2TreeNode完成了 LeetCode 层序输入到 Go 树对象的映射gotest.sh提供了一条命令跑完全部题目并生成覆盖率报告。掌握分岔判定 单侧递归的模式后你可以把它直接迁移到BST 中找第 k 小BST 中找区间和等同类值域导向的题目中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考