题目描述

给定一棵二叉树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

tree

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解题思路

方法1

递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr){
            return nullptr;
        }
        if(root==p || root==q){
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left!=nullptr && right!=nullptr){
            return root;
        }
        if(left!=nullptr)
            return left;
        if(right!=nullptr)
            return right;

        return nullptr;
    }
};

方法2

1. 遍历二叉树，得到每个节点的父节点，这样一个hash表；
2. 从p节点出发，遍历得到由p节点到根节点，这样父节点的路径(用hash表表示，节点对应值为true表示在路径上)；
3. 从q节点，查看是否在上述路径中，若在则表示找到最近公共祖先。

unordered_map<int, TreeNode*> fa;
unordered_map<int, bool> vis;

void dfs(TreeNode* root){
    if(root->left!=nullptr){
        fa[root->left->val] = root;
        dfs(root->left);
    }
    if(root->right!=nullptr){
        fa[root->right->val] = root;
        dfs(root->right);
    }
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
    fa[root->val] = nullptr;
    dfs(root);
    while(p!=nullptr){
        vis[p->val] = true;
        p = fa[p->val];
    }
    while(q!=nullptr){
        if(vis[q->val])
            return q;
        q = fa[q->val];
    }
    return nullptr;
}