python给定一个二叉树和两个节点，实现一个函数，找到这两个节点的最近公共祖先。最近公共祖先是指离这两个节点最近的、同时是它们祖先的节点。验证你的实现是否正确，通过对二叉树进行先序遍历、中序遍历、后序遍历和层次遍历，找到给定节点的最近公共祖先实现代码

以下是实现代码：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    if root.val == p.val or root.val == q.val:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left is not None and right is not None:
        return root
    elif left is None:
        return right
    else:
        return left

# 验证代码是否正确
def preorder(root):
    if root is None:
        return
    print(root.val, end=" ")
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.val, end=" ")
    inorder(root.right)

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val, end=" ")
   
def levelorder(root):
    if root is None:
        return
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.val, end=" ")
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

# 构造一个测试树
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

# 找到最近公共祖先并输出
p = TreeNode(5)
q = TreeNode(1)
ancestor = lowestCommonAncestor(root, p, q)
print(f"最近公共祖先：{ancestor.val}")

# 验证代码正确性
print("先序遍历：", end="")
preorder(root)
print("\n中序遍历：", end="")
inorder(root)
print("\n后序遍历：", end="")
postorder(root)
print("\n层次遍历：", end="")
levelorder(root)

运行结果如下：

最近公共祖先：3
先序遍历：3 5 6 2 7 4 1 0 8 
中序遍历：6 5 7 2 4 3 0 1 8 
后序遍历：6 7 4 2 5 0 8 1 3 
层次遍历：3 5 1 6 2 0 8 7 4