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

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

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
471
粉丝
21
喜欢
37
收藏
22
排名:457
访问:1.9 万
私信
所有博文
社区赞助商