剑指 Offer 68 - II. 二叉树的最近公共祖先

题目来源：https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

大致题意：
给一颗二叉树和两个节点 p 和 q，求二叉树中 p 和 q 的最近公共祖先

思路

使用递归的方式可以寻找二叉数的某个节点，查找的过程中可以使用标志位表示对应节点是否找到

同理对于该题，首先要查找到节点 p 和 q，然后通过两个标志位让父节点知道子树中是否包含对应节点

首先考虑查找两个节点的公共祖先，该方法的执行逻辑为：

1. 使用一个大小为 2 的结果数组表示子树的查找情况
2. 判断当前节点是否为空，若为空直接返回
3. 递归左子树、右子树，根据递归结果更新结果数组
4. 根据当前节点是否是 p 或者 q，更新结果数组
5. 如果当前结果数组两个元素都为真，表示当前节点为祖先节点

上述方法可以找到两个节点的所有公共祖先，那么如何查找最近公共祖先？

根据递归栈的调用过程，第一个找到的祖先节点即为最近公共祖先，所以可以额外使用标志位表示最近公共祖先是否找到，改进后的执行逻辑为：

1. 使用一个大小为 2 的结果数组表示子树的查找情况
2. 首先判断当前子树是否为空，或者两个节点是否都找到，如果都找到表明当前节点一定不是最近公共祖先，直接剪枝
3. 递归查找子树，并根据子树结果更新结果数组
4. 判断当前节点是否是 p 或者 q，更新结果数组
5. 如果截至当前节点，表示最近公共祖先是否找到的标志位为 false，且当前结果数组元素都为真，表明当前节点即为最近公共祖先

具体看代码：

class Solution {
    boolean isFind; // 标记最近公共祖先是否找到
    TreeNode ans;   // 最近公共祖先
    TreeNode p;
    TreeNode q;
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs(root);
        return ans;
    }

    public boolean[] dfs(TreeNode node) {
        boolean[] res = new boolean[2];
        // 如果节点为空或者最近公共祖先已找到
        if (node == null || isFind) {
            return res;
        }
        // 递归查找子树
        boolean[] left = dfs(node.left);
        boolean[] right = dfs(node.right);
        res[0] = left[0] | right[0];
        res[1] = left[1] | right[1];
        // 根据节点值更新结果数组
        if (node.val == p.val) {
            res[0] = true;
        }
        if (node.val == q.val) {
            res[1] = true;
        }
        // 如果最近公共祖先还未找到，且当前结果数组元素都为真，则当前节点为最近公共祖先
        if (!isFind && res[0] && res[1]) {
            isFind = true;
            ans = node;
        }
        return res;
    }
}