题目的主要信息：

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

方法一：

采用递归。用dfs进行深度优先搜索，首先判断当前结点root是否为NULL，如果不为NULL，就在它的组有子树中递归查找，如果两个节点分别在左右子树中，或者root值为其中一个，另一个值在子树中，则root为最近公共祖先。如果左右子树中有，或者等于当前结点值，则返回true。

具体做法：

class Solution {
public:
    TreeNode* ans;//最近公共组先
    bool dfs(TreeNode* root, const int& p, const int& q) {
        if (root == NULL){
            return false;
        }
        bool ls = dfs(root->left, p, q);//左子树中递归查找
        bool rs = dfs(root->right, p, q);//右子树中递归查找
        if ((ls && rs) || ((root->val == p || root->val == q) && (ls || rs))){
            //如果分别在左右子树，或者根结点值为其中一个，另一个值在子树中
            ans = root;
        }
        return ls || rs || (root->val == p || root->val == q);//在左子树或者右子树或者当前值为p、q返回true
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        dfs(root, o1, o2);//递归
        return ans->val;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要递归遍历所有结点。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。

方法二：

首先分别找到从根节点到两个指定节点的路径。查找路径用的是findTargetNode函数，用path记录下路径，每次递归先判断root是否为NULL，如果为NULL的话表示从根节点一直到叶子结点都没有找到指定节点，当前路径行不通，需要回溯；如果root不为NULL，首先判断root是否为指定节点，如果是指定节点，说明找到了一条路径，结束递归；如果root不是指定节点，就往左右子树继续递归查找。

找到从根节点到两个指定节点的路径path1和path2后，遍历一遍两个路径，找到两个路径中的最后一个相同的节点就是他们的最近公共祖先。 具体做法：

class Solution {
public:
    void findTargetNode(TreeNode* root, vector<int>& path, int target) {
        if (!root) return;//如果root为NULL结束递归
        path.push_back(root->val);
        if (root->val == target) {
            // 找到了，结束递归
            return;
        }
        findTargetNode(root->left, path, target);
        if (path.back() == target) return;
        // 在右子树搜索
        findTargetNode(root->right, path, target);
        if (path.back() == target) return;
        path.pop_back();//回溯
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        vector<int> path1;
        findTargetNode(root, path1, p);//找到从root到p的路径
        vector<int> path2;
        findTargetNode(root, path2, q);//找到从root到q的路径
        int l = 0;
        while (l < path1.size() && l < path2.size() && path1[l] == path2[l]) {
            l++;
        }//找到最后一个相同节点
        return path1[l - 1];
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要递归遍历所有结点。
• 空间复杂度：$O(n)O(n)$，路径向量大小为n。