二叉树的最近公共祖先

package main

import "fmt"

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    // 如果当前节点是 p 或 q，则它本身就是最近公共祖先
    if root == p || root == q {
        return root
    }

    // 在左子树中递归寻找最近公共祖先
    left := lowestCommonAncestor(root.Left, p, q)

    // 在右子树中递归寻找最近公共祖先
    right := lowestCommonAncestor(root.Right, p, q)

    // 如果左右子树分别找到 p 和 q，则当前节点是最近公共祖先
    if left != nil && right != nil {
        return root
    }

    // 如果左子树找到 p 或 q，则返回左子树的结果
    if left != nil {
        return left
    }

    // 如果右子树找到 p 或 q，则返回右子树的结果
    return right
}

func main() {
    // 创建一个二叉树
    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.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}

    // 定义两个节点
    p := root.Left
    q := root.Left.Right.Right

    // 找到最近公共祖先
    result := lowestCommonAncestor(root, p, q)

    // 输出最近公共祖先的值
    fmt.Printf("节点 %d 和节点 %d 的最近公共祖先是节点 %d\n", p.Val, q.Val, result.Val)
}