https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=problem-list-v2&envId=2cktkvj

解题思路：

利用深度优先搜索，把所有节点的父节点存入parent map中

然后再查找p的父节点，标记为visted

然后再查找q的父节点（从下往上）,查找到了就说明这是两个二叉树的公共祖先，直接返回

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    parent := map[int]*TreeNode{}
    visited := map[int]bool{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        if node.Left != nil {
            parent[node.Left.Val] = node
            dfs(node.Left)
        }
        if node.Right != nil {
            parent[node.Right.Val] = node
            dfs(node.Right)
        }
    }
    dfs(root)
    for p != nil {
        visited[p.Val] = true
        p = parent[p.Val]
    }
    for q!= nil {
        if visited[q.Val] {
            return q
        }
        q = parent[q.Val]
    }
    return nil
}