2024-03-13：用 go 语言，给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q =

作者：福大大架构师每日一题

2024-03-13
北京
本文字数：1564 字
阅读完需：约 5 分钟

2024-03-13：用 go 语言，给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8。

输出: 6。

答案 2024-03-13：

来自左程云。

灵捷3.5

大体步骤如下：

1.首先，我们需要遍历树来找到这两个节点。从根节点开始，若两个节点都比当前节点的值小，则它们一定在当前节点的左子树中。若两个节点都比当前节点的值大，则它们一定在当前节点的右子树中。如果以上两种情况都不成立，那么说明一个节点在左子树中，另一个节点在右子树中，那么当前节点就是它们的最近公共祖先。

2.为了解决这个问题，我们可以使用迭代方法。从根节点开始，比较当前节点的值与给定节点的值。根据比较结果，不断移动到左子树或右子树，直到满足上述公共祖先的情况，即找到最近的公共祖先。

总的时间复杂度：

在最坏情况下，我们需要遍历整棵树，时间复杂度为 O(n)，其中 n 是树中节点的数量。

总的额外空间复杂度：

迭代方法的空间复杂度是 O(1)，因为我们只使用了常数级别的额外空间。

综上所述，总的时间复杂度为 O(n)，总的额外空间复杂度为 O(1)。

go 完整代码如下：

package main
import "fmt"
type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}
// lowestCommonAncestor 用于找到二叉搜索树中两个节点的最近公共祖先func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {    for root.Val != p.Val && root.Val != q.Val {        if (min(p.Val, q.Val) < root.Val) && (root.Val < max(p.Val, q.Val)) {            break        }        if root.Val < min(p.Val, q.Val) {            root = root.Right        } else {            root = root.Left        }    }    return root}
func min(x, y int) int {    if x < y {        return x    }    return y}
func max(x, y int) int {    if x > y {        return x    }    return y}
func main() {    // 创建二叉搜索树    root := &TreeNode{Val: 6}    root.Left = &TreeNode{Val: 2}    root.Right = &TreeNode{Val: 8}    root.Left.Left = &TreeNode{Val: 0}    root.Left.Right = &TreeNode{Val: 4}    root.Right.Left = &TreeNode{Val: 7}    root.Right.Right = &TreeNode{Val: 9}    root.Left.Right.Left = &TreeNode{Val: 3}    root.Left.Right.Right = &TreeNode{Val: 5}
    // 定义p和q    p := &TreeNode{Val: 2}    q := &TreeNode{Val: 8}
    // 调用lowestCommonAncestor函数    result := lowestCommonAncestor(root, p, q)
    // 输出结果    fmt.Printf("最近公共祖先的值为：%d\n", result.Val)}

复制代码

python 完整代码如下：

# -*-coding:utf-8-*-
class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = None
def lowestCommonAncestor(root, p, q):    while (root.val - p.val) * (root.val - q.val) > 0:        root = (root.right, root.left)[p.val > root.val]    return root
def main():    # 创建二叉搜索树    root = TreeNode(6)    root.left = TreeNode(2)    root.right = TreeNode(8)    root.left.left = TreeNode(0)    root.left.right = TreeNode(4)    root.right.left = TreeNode(7)    root.right.right = TreeNode(9)    root.left.right.left = TreeNode(3)    root.left.right.right = TreeNode(5)
    # 定义p和q    p = TreeNode(2)    q = TreeNode(8)
    # 调用lowestCommonAncestor函数    result = lowestCommonAncestor(root, p, q)
    # 输出结果    print("最近公共祖先的值为：", result.val)
if __name__ == "__main__":    main()