题目

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

题解

两个方法

1. 递归+后序遍历

直接用后续遍历对二叉树进行遍历，每次返回有以下几种情况

  1. 若该节点为nullptr，或者该节点为p或者q，则直接返回
  2. 判断该节点的左右两节点的情况
    1. 若左右两个节点递归返回都为nullptr，则返回nullptr。此时说明该节点左右都没有p或者q
    2. 若左节点为nullptr，右节点不为空，则返回右节点。此时说明其右子树有p或q
    3. 若右节点为nullptr，左节点不为空，则返回左节点。此时说明其左子树有p或q
    4. 若左右都不为nullptr，说明找到了公共祖先，直接返回。（此结果会返回到递归的顶层，并作为最终的返回结果。因为其在返回过程中另一半始终为nullptr
  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$，递归
class Solution {//两个方法。1. 后续遍历+递归
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;//1
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        //1.1包含在以下两行
        if(left == nullptr) return right;//1.2
        if(right == nullptr) return left;//1.3
        else return root;//1.4
    }
};

2. 反推路径法

看注释吧

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {//2.反向遍历找交点
    //存父节点用于反向倒退根节点
    unordered_map<TreeNode*, TreeNode*> father;
    //存p或者q反向倒推根节点时的路径上的节点
    unordered_set<TreeNode*> s;
public:
    //遍历二叉树，存所有节点的父节点
    void dfs(TreeNode* cur){
        if(cur->left){
            father[cur->left] = cur;
            dfs(cur->left);
        }
        if(cur->right){
            father[cur->right] = cur;
            dfs(cur->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //将根节点的父节点设置为空
        father[root] = nullptr;
        dfs(root);//找所有节点的父节点
        //从p反推到根节点，并存储路径上的所有节点
        while(p){
            s.insert(p);
            p = father[p];
        }
        //从q反推到根节点，遇到p路径上的节点直接返回
        while(q){
            if(s.count(q)) return q;
            q = father[q];
        }
        return nullptr;
    }
};