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

首先要明确题意，既寻找给定非空二叉树中的两个节点的最近公共祖先节点
祖先：若节点 o1 在 root的左子树/右子树上，或 o1 = root， 则 root 为 o1 祖先

答案为1

核心代码：

class Solution {
public:
    bool find = false; //标记是否找到了

    void dfs(vector<int>& load, TreeNode* root, int o) {
        if(find || root == nullptr) return; //已经找到或者到达空节点
        load.push_back(root->val); //加入数组
        if(root->val == o) {
            find = true;
            return;
        }
        dfs(load, root->left, o);
        dfs(load, root->right, o);
        if(find) { //防止将节点去除
            return;
        }
        load.pop_back(); //不在这条路径，去除节点
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> load1, load2;
        dfs(load1, root, o1); //找到 root到o1路径
        find = false; //重置标记
        dfs(load2, root, o2); //找到 root到o2路径
        int leng = min(load1.size(), load2.size());
        //寻找最后一个相等节点
        for(int i = 1; i < leng; ++i) {
            if(load1[i] != load2[i]) {
                return load1[i - 1]; 
            }
        }
        return load1[leng - 1];
    }
};

复杂度分析：
时间复杂度：$O（n)$，n为树的节点数，因为需要进行两次深度搜索，每次最多搜索一个节点一次
空间复杂度：$O（n）$， 需要两个数组以及深度搜索的栈空间

方法二：递归
核心思想：
分析可知，对于节点 o1, o2 的最近公共祖先，只存在三种情况：

1. o1 ，o2 分别位于root的左右子树上
   
2. o1 = root, 且 o2 位于root的左子树/右子树中
   
3. o2 = root, 且 o1 位于root的左子树/右子树中
   
   于是，可以通过递归解决本题

递归情况：
1.当到达空节点（既叶子节点的子节点）时，直接返回空
2.当root等于 o1 或 o2 时，返回root
3.若不为1， 2中情况，说明需要继续处理：
对左子树进行递归，返回值记为 t1
对右子树进行递归，返回值记位 t2
t1 ，t2 存在以下几种情况：
①. 当t1, t2都为空时，说明root的左右子树中都不存在o1, o2， 返回空
②. 当t1为空且t2不为空时，说明左子树找不到 o1, o2,所以返回 t2
③. 当t2为空且t1不为空时，说明右子树找不到 o1, o2,所以返回 t1
④. 当t1, t2都不为空时,说明o1, o2分别位于root的左右子树中，既root为答案，返回root
核心代码：

class Solution {
public:
    TreeNode* dfs(TreeNode* root, int o1, int o2) {
        if(root == nullptr) return nullptr; //超过叶节点，返回空
        if(root->val == o1 || root->val == o2) return root; //节点为其中一个
        TreeNode* t1 = dfs(root->left, o1, o2);
        TreeNode* t2 = dfs(root->right, o1, o2);
        if(t1 == nullptr) return t2; //此时两个节点都在右侧
        if(t2 == nullptr) return t1; //此时两个节点都在左侧
        return root; //此时两个节点分别位于左右两侧
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        return dfs(root, o1, o2)->val;
    }
};

复杂度分析：
时间复杂度：$O（n)$,n为树的节点数，最多访问每个节点一次
空间复杂度：$O（n）$，空间复杂度取决于递归的栈深。最差情况下，数退化为链表，树高为n,故需要O(n)空间