算法：二叉树中两个节点的最低公共祖先（LCA）

2024-07-30 08:13:33 浏览数 (2)

思路

要找到一个二叉树中两个节点的最低公共祖先（Lowest Common Ancestor, LCA），需要考虑以下几点：

  1. 定义LCA：对于节点 A 和 B，它们的LCA是指在二叉树中同时作为 A 和 B 的祖先的最低节点。也就是说，LCA X 满足 X 是 A 和 B 的祖先，并且 X 的深度尽可能大。
  2. 递归解法：采用递归的方式可以有效地找到 LCA：
    • 如果当前节点为 null $，则返回 null $。
    • 如果当前节点等于 A 或 B $，则返回当前节点，因为自身可以是自己的祖先。
    • 递归地在左子树和右子树中寻找 A 和 B 的 LCA。
    • 如果左右子树分别返回非空（即 A 和 B 分别在左右子树中找到），则当前节点即为 LCA。
    • 如果只有一边找到了非空（例如只在左子树找到了 LCA），则说明 LCA 在这个非空的子树中。

Go实现示例

下面是用 Go 实现二叉树中两个节点的最低公共祖先（LCA）可以采用递归的方法，这里假设已经定义了二叉树节点的结构体：

代码语言：go复制
package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, A, B *TreeNode) *TreeNode {
    // Base case: if root is nil or equal to A or B, return root
    if root == nil || root == A || root == B {
        return root
    }
    
    // Recursively search left and right subtrees for LCA
    leftLCA := lowestCommonAncestor(root.Left, A, B)
    rightLCA := lowestCommonAncestor(root.Right, A, B)
    
    // If both leftLCA and rightLCA are non-nil, then root is the LCA
    if leftLCA != nil && rightLCA != nil {
        return root
    }
    
    // Otherwise, LCA is either in left subtree or right subtree
    if leftLCA != nil {
        return leftLCA
    }
    return rightLCA
}

func main() {
    // Example usage:
    // Construct a binary tree
    //        3
    //       / 
    //      5   1
    //     /  / 
    //    6  2 0  8
    //      / 
    //     7   4
    
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    
    // Nodes for which we want to find LCA
    A := root.Left   // Node with value 5
    B := root.Right  // Node with value 1
    
    // Find LCA of A and B
    lca := lowestCommonAncestor(root, A, B)
    if lca != nil {
        fmt.Println("Lowest Common Ancestor of", A.Val, "and", B.Val, "is", lca.Val)
    } else {
        fmt.Println("No common ancestor found for", A.Val, "and", B.Val)
    }
}

在这个示例中，lowestCommonAncestor 函数使用递归的方式来查找节点 A 和 B 的 LCA。在 main 函数中，构造了一个二叉树，并找到了节点 5 和节点 1 的最低公共祖先。

这段代码输出的结果应该是：

代码语言：bash复制
$ Lowest Common Ancestor of 5 and 1 is 3

这表明节点 5 和节点 1 的最低公共祖先是节点 3。

复杂度分析

在给定的解决方案中，时间复杂度是 O(n)，其中 n 是二叉树中节点的数量。

  1. 时间复杂度：
    • 在最坏情况下，递归函数 lowestCommonAncestor 可能会访问每个节点一次。这是因为在最差情况下，需要遍历整棵树来查找给定的两个节点 p 和 q。
    • 因此，递归函数的时间复杂度为 O(n)，其中 n 是树中节点的总数。
  2. 空间复杂度：
    • 递归调用的空间复杂度取决于递归栈的深度，最坏情况下为 O(h)，其中 h 是树的高度。对于一棵平衡二叉树，h 是 O(log n)，但对于一棵非平衡二叉树，h 可能是 O(n)。
    • 在最坏情况下，递归调用的空间复杂度为 O(n)。

因此，整体来说，通过递归遍历二叉树来寻找两个节点的最低公共祖先的时间复杂度是 O(n)，这保证了算法在合理的时间范围内解决问题，适用于一般大小的二叉树。

go 算法 腾讯技术创作特训营S8

0 人点赞