//二叉树
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
    
    func  equal(_ root: TreeNode?) -> Bool {
        return (self.val == root?.val) && (self.left?.val == root?.left?.val) && (self.right?.val == root?.right?.val)
    }
}

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    if root?.val == nil || root!.equal(p) || root!.equal(q) {
        return root
    }
    
    let left:TreeNode? = lowestCommonAncestor(root!.left, p, q)
    
    let right: TreeNode? = lowestCommonAncestor(root!.right, p, q)
    
    if left?.val != nil && right != nil {
        return root
        
    }
    
    return left?.val != nil ? left : right
    
}