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

• 1. 问题描述
• 2. 样例说明
• 3. 解法一：递归
• • 算法思想
  • 代码
  • 时间空间复杂度分析
• 4. 解法二：非递归
• • 算法思想
  • 代码
  • 时间空间复杂度分析

1. 问题描述

2. 样例说明

3. 解法一：递归

算法思想

分析可知，对于节点 o1, o2 的最近公共祖先，只存在三种情况：

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

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; //t1找不到o1,o2
        if(t2 == nullptr) return t1; //t2找不到o1,o2
        return root; //此时两个节点分别位于左右两侧
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        return dfs(root, o1, o2)->val;
    }
};

时间空间复杂度分析

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

4. 解法二：非递归

算法思想

对root进行两次深度搜索，分别找到到达 o1 和 o2 的路径，两条路径的最后一个公共节点即为最近公共祖先

代码

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）， 需要两个数组以及深度搜索的栈空间