[数据结构与算法](day 52 - DFS) 剑指 Offer 68 - II. 二叉树的最近公共祖先

题目

题链：剑指 Offer 68 - II. 二叉树的最近公共祖先添加链接描述

题解

K神大佬详细题解：剑指 Offer 68 - II. 二叉树的最近公共祖先（DFS ，清晰图解）
本题和他的一版本不同的是这个不是排序二叉树、所以只能用DFS了。
DFS时、终止条件是遍历到叶节点没找到返回null、找到了直接返回那个节点，然后回栈到上一节点的时候要加判断条件

1. 假设这个节点左右节点都不是空说明这个节点就是最近公共祖先，直接返回这个节点。
2. 假设只有左子树为空、右子树不为空说明有一个节点在这个节点的右子树上或者最近公共节点在这个节点的右子树上。
3. 假设只有右子树为空、左子树不为空同2条件一样。
4. 假设左右节点都为空说明不在这个节点下。

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