题解 | #在二叉树中找到两个节点的最近公共祖先#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int ans = NULL;
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        dfs(root, p, q);
        return ans;
    }

    int dfs(TreeNode* root, int p, int q) {
        if (!root) return 0;
        int state = dfs(root->left, p, q);  // 左子树遍历的结果
        if (root->val == p) state |= 1;  // 二进制个位数1代表p
        else if (root->val == q) state |= 2;  // 二进制十位数2代表q
        state |= dfs(root->right, p, q);  //右子树遍历的结果
        if (state == 3 && !ans) ans = root->val;  // 如果等于说明当前节点有pq  ans没有赋过值就还是NULL说明当前子树是第一个包含pq说明当前根节点就是他们公共祖先
        return state;
    }
};