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

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

输出: 6。

答案2024-03-13：

大体步骤如下：

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()