题链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
题描述：
解题思路：
利用 DFS，对每个节点进行左右子节点的遍历，利用变量 res 保存最近公共祖先节点，利用变量 flag 记录当前节点的子树是否有 p 或者 q，在遍历完左右子节点后，如果当前节点是 p 或 q 中的一个，也让 flag 记录（因为一个节点也可以是它自己的祖先）。如果 p 和 q 都在该节点的子树中，且 res 还是初始状态，则该节点就是最终结果。在 dfs 函数的返回值方面，我们使用 return 1 表示子树中有 p 或 q。
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode res = new TreeNode();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
res.val = -1;
int t = dfs(root, p, q);
return res;
}
public int dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || res.val != -1) {
return 0;
}
int flag = 0;
if (dfs(root.left, p, q) == 1) {
flag++;
}//遍历左子节点
if (dfs(root.right, p, q) == 1) {
flag++;
}//遍历右子节点
if (root == p || root == q) {
flag++;
}//一个节点也可以是它自己的祖先
if (flag == 2 && res.val == -1) {
res = root;
}//res节点仍是初始状态且当前节点满足要求
if (root == p || root == q || flag > 0) {
return 1;
}//子树中有 p 或 q 节点
return 0;//子树中不存在 p 或 q 节点
}
}
时间复杂度：O(n)
空间复杂度：O(n)
