leetcode236求最近公共祖先

• 递归

TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode* q){
    if(!root)return root;//当发现这个节点已经是叶节点时，要告诉上层
    if(root==p||root==q)return root;//当发现是p节点或者q时也要告诉上层
    TreeNode* left=dfs(root->left,p,q);//左子树是否有p或者q
    TreeNode* right=dfs(root->right,p,q);//右子树是否有
    if(left&&right)return root;
    if(left&&!right)return left;
    if(right&&!left)return right;//说明现在的子树的根节点是 p或者q，而右子树没有p或者q，说明p、q是在一个子树上
    return nullptr;
}

•  用哈希表存每个节点的父节点，然后找p节点开始从下而上遍历，走过的就标记。再重复从q从上而下遍历只要遇见之前已经走过的节点就返回为公共祖先。

unordered_map<int ,TreeNode*>f;
unorederd_map<int,bool>vis;
void dfs(TreeNode* root){
    if(root->left){
        f[root->left]=root;
        dfs(root->left);
    }
    if(root->right){
        f[root->right]=root;
        dfs(root->right);
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
    f[root->val]=nullptr;
    while(p){
        vis[p->val]=true;
        p=f[p->val];
    }
    while(q){
        if(vis[q->val])return q;
        q=f[q->val];
    }
    return nullptr;//没有公共祖先
}