给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

1.递归。一个节点如果是两个节点的公共祖先的话，那么有两种情况：

        (1)这个节点的左子树包含其中一个节点，并且右子树包含另一个节点。

        (2)这个节点本身是其中一个节点，另一个节点在当前节点的左子树或右子树上。

   用一个boolean值来表示当前节点是否含有两个节点中一个，并且递归是从下往上进行的，找到的肯定就是最近的公共祖先。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode ans = null;//定义一个全局变量存储最近公共节点

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return ans;
    }

    public boolean dfs(TreeNode root,TreeNode p,TreeNode q) {
        if(root == null){//如果节点为null，返回false
            return false;
        }

        boolean left = dfs(root.left,p,q);//判断左子树是否包含p或q
        boolean right = dfs(root.right,p,q);//判断右子树是否包含p或q
        //最近公共节点的条件
        //1.左子树包含其中一个，并且右子树包含另一个
        //2.当前根结点是其中一个，并且另一个在左子树上或者在右子树上
        if((left && right) || ((root.val == p.val || root.val == q.val) && (left || right))){
            ans = root;
        }
        //判断每个节点是否含有p或q
        return left || right || (root.val == p.val || root.val == q.val);
    }
}

        递归的优化：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {//当前根节点为null，返回null
            return null;
        }

        if (root == p || root == q) {//如果根节点是p或者q，那么最近公共祖先就是这个根节点
            return root;
        }

        //找到含有p或q的最小的子树
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if (left != null && right != null) {//说明分布在左右子树上，当前根节点就是最近的
            return root;
        }
        //说明p、q分布在同一侧子树上，就是非空的那个子树
        return left != null ? left : right;
    }
}

2.用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

class Solution {
    Map<Integer,TreeNode> parent = new HashMap<>();//存储每个节点的父节点
    Set<TreeNode> visited = new HashSet<>();//存储从一个节点本身向上访问的节点路径

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);//把每个节点及其父节点的的关系存储到哈希表中

        while(p != null){//存储p从下往上的访问顺序
            visited.add(p);
            p = parent.get(p.val);
        }

        while(q != null){//从下往上q的访问顺序
            if(visited.contains(q)){//如果访问到p的访问路径中含有的节点，就是最近公共祖先，返回
                return q;
            }
            q = parent.get(q.val);
        }

        return null;
    }

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

题源：力扣