1、思路

• 遍历二叉树，寻找给定的两个节点p和q，找到后直接返回该节点，不再往下遍历了；

• 遍历到的每个节点分三种情况处理：
  1、当前节点的左右子树中分别存在给定节点，则当前节点就是首个公共祖先；
  2、当前节点只有左子树中存在给定节点，返回此左子树节点；
  3、当前节点只有右子树中存在给定节点，返回此右子树节点；

2、代码

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;

        if (root == p || root == q) return root;                //找到给定节点

        auto left = lowestCommonAncestor(root->left, p, q);     //遍历左右子树
        auto right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root; // 1.
        else if (left) return left;     // 2.
        else return right;              // 3.
    }
};