今天刷的是这题，属于中等题，我是直接看的题解，官方给出了两种方法

第一种是递归，直接看代码吧

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {}return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        if (left == null) return right;
        return left;
    }
}

这段代码的意思大概如下：

1.如果当前节点是p,或者当前节点是q，或者当前节点是空节点则返回当前节点

2.左右子树都找到则返回当前节点

3.只有左子树找到则返回递归左子树的结果

4.只有右子树找到则返回递归右子树的结果

5.左右子树都没有找到则返回空节点

为了加深对递归的理解，我画了个这图如下，主要体现递归时参数传递和返回值的流动，下面的图是以寻找节点4和节点8的最近公共祖先为例

第二种是存储父节点，利用HashMap存储所有节点的父节点，key是当前节点的值，value是当前节点的父节点，然后利用HashSet来记录访问的节点，从p节点开始往上依次访问，访问过的节点放到HashSet中，接着从q节点依次向上访问，如果遇到访问过的节点，那么此节点就是p和q的最近公共祖先节点，首先代码如下

class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}

 题目链接：https://leetcode.cn/problem-list/2cktkvj/