题目的主要信息：

• 给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点
• 二叉树非空，且每个节点值均不同

方法一：路径比较法

具体做法：

利用dfs求得根节点到两个目标节点的路径，然后遍历两条路径依次比较，找到两条路径第一个不相同的节点即是最近公共祖先。

class Solution {
public:
    bool flag = false; //记录是否找到到o的路径
    void dfs(TreeNode* root, vector<int>& path, int o){ //求得根节点到目标节点的路径
        if(flag || root == NULL)
            return;
        path.push_back(root->val);
        if(root->val == o){ //节点值都不同，可以直接用值比较
            flag = true;
            return;
        }
        dfs(root->left, path, o); //dfs遍历查找
        dfs(root->right, path, o);
        if(flag)
            return;
        path.pop_back(); //该子树没有，回溯
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> path1, path2; 
        dfs(root, path1, o1); //求根节点到两个节点的路径
        flag = false; //重置flag
        dfs(root, path2, o2);
        int res ; 
        for(int i = 0; i < path1.size() && i < path2.size(); i++){ //比较两个路径，找到第一个不同的点
            if(path1[i] == path2[i]) 
                res = path1[i]; //最后一个相同的节点就是最近公共祖先
            else
                break;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为节点数，递归遍历二叉树每一个节点求路径，后续又遍历路径
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，深度为$nn$，递归栈深度和路径数组为$nn$

方法二：递归

具体做法：

我们可以从根节点开始遍历，如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        if(root == NULL) //该子树没找到，返回-1
            return -1;
        if(root->val == o1 || root->val == o2) //该节点是其中某一个节点
            return root->val;
        int left = lowestCommonAncestor(root->left, o1, o2); //左子树寻找公共祖先
        int right = lowestCommonAncestor(root->right, o1, o2); //右子树寻找公共祖先
        if(left == -1) //左子树为没找到，则在右子树中
            return right;
        if(right == -1) //右子树没找到，则在左子树中
            return left;
        return root->val; //否则是当前节点
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为节点数，递归遍历二叉树每一个节点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，深度为$nn$，递归栈深度为$nn$