2024-03-13：用go语言，给定一个二叉搜索树, 找到该树中两个指定

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完整代码如下：

packagemain
import"fmt"
typeTreeNodestruct{
Valint
Left*TreeNode
Right*TreeNode
}
//lowestCommonAncestor用于找到二叉搜索树中两个节点的最近公共祖先
funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{
forroot.Val!=p.Val&&root.Val!=q.Val{
if(min(p.Val,q.Val)break
}
ifroot.Valroot=root.Right
}else{
root=root.Left
}
}
returnroot
}
funcmin(x,yint)int{
ifxreturnx
}
returny
}
funcmax(x,yint)int{
ifx>y{
returnx
}
returny
}
funcmain(){
//创建二叉搜索树
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-*-
classTreeNode:
def__init__(self,x):
self.val=x
self.left=None
self.right=None
deflowestCommonAncestor(root,p,q):
while(root.val-p.val)*(root.val-q.val)>0:
root=(root.right,root.left)[p.val>root.val]
returnroot
defmain():
#创建二叉搜索树
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()