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;//没有公共祖先
}