js
package main

import (
	"fmt"
)

// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

// 最近公共祖先的定义：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
// 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

// 例如，如下二叉树:  Integer[] levelOrder = {3,5,1,6,2,0,8,null,null,7,4};
//           3
//     5          1
//  6     2    0     8
//      7   4

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

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.Right.Left
	q := root.Left.Right.Right
	lca := lowestCommonAncestor(root, p, q)
	fmt.Println("最近公共祖先:", lca.Val)

	// fmt.Println("Hello world!")
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	return right
}