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

方法一：DFS、路径比较

1、利用深度优先搜索分别获取两个结点在二叉树中的路径；

2、比较两个路径，得到最后相同的的结点即为两个结点的最近公共祖先。

时间复杂度：o(n)。最坏情况需要遍历二叉树所有节点

空间复杂度：o(n)。

class Solution {
  public:
    bool flag = false;
    //深度优先搜索（dfs）
    void dfs(TreeNode* root, vector<int>& path, int target) {
        if (root == nullptr || flag == true)
            return;

        path.push_back(root->val);
        if (root->val == target) {
            flag = true;
            return;
        }
        dfs(root->left, path, target);
        dfs(root->right, path, target);

        if (flag == true)
            return;
        //如果到达底部还未找到，回溯
        path.pop_back();
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> path1;
        vector<int> path2;

        dfs(root, path1, o1);
        //重置flag寻找下一个
        flag = false;
        dfs(root, path2, o2);

        int num;
        //寻找最后一个相同的结点
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1[i] == path2[i])
                num = path1[i];
        }

        return num;
    }
};

方法二：递归

• step 1：如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。
• step 2：如果都不匹配，则分别递归左、右子树。
• step 3：如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.
• step 4：如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。
• step 5：继续递归左、右子树，直到遇到step1或者step3的情况。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        //该子树没找到，返回-1
        if(root == NULL) 
            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; 
    }
};