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

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