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

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

在这里插入图片描述