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

设置dfs函数寻找其中 cur 为当前处理到的节点，t 为需要找到的目的节点，path 为从根节点到当前节点 cur 所经过的路径。若能够以当前节点 cur 为根的子树包含目标节点 t，函数返回 true，否则返回 false。
调用函数分别传入 p 和 q 作为目标节点，从而得到从根节点到 p 和 q 的路径列表，遍历路径找到最后一个相同的节点即是答案。

class Solution {
  public:
    bool dfs(TreeNode* cur, int  t, vector<TreeNode*>& path) {
        if (!cur) return false;
        path.push_back(cur);
        if (cur->val == t || dfs(cur->left, t, path) || dfs(cur->right, t, path)) {
            return true;
        } else {
            path.pop_back();
            return false;
        }
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<TreeNode*> a, b;
        dfs(root, o1, a);
        dfs(root, o2, b);
        TreeNode* ans = nullptr;
        for (int i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) ans = a[i];
        return ans->val;

    }
};