最开始做的时候，就先想到的是找父节点的那个函数，于是先把目标节点的所以祖先节点存起来，然后一个一个进行比对，当然这样耗时很大。
点击查看代码
class Solution {
public:
vector<TreeNode*>vp,vq;
TreeNode*findfa(TreeNode*root,TreeNode*k){
if(!root){return NULL;}
if(root==k||root->left==k||root->right==k){return root;}
TreeNode*mleft=findfa(root->left,k);
if(mleft){return mleft;}
else{return findfa(root->right,k);}
return NULL;
}
void allfa(TreeNode*root,TreeNode*k,vector<TreeNode*>&cnt){
if(root==k){
cnt.push_back(k);
return ;
}
cnt.push_back(k);
allfa(root,findfa(root,k),cnt);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
allfa(root,p,vp);
allfa(root,q,vq);
for(int i=0;i<vp.size();i++){
for(int j=0;j<vq.size();j++){
if(vp[i]==vq[j]){return vp[i];}
}
}
return NULL;
}
};
后面看了卡哥的方法，虽然有点难想，但还是可以学习模仿。
一般的题目是从根节点开始往叶节点去找，但这题要求是要从叶节点往根节点找，把目标节点不断往上传递。这就显然要用后序遍历了。
两步走，终止条件，单层递归逻辑
终止条件，就想三个节点。
点击查看代码
if(!root){return NULL;}
if(root==p||root==q){return root;}
点击查看代码
if(leftflag&&rightflag){return root;}
else if(!leftflag&&rightflag){return rightflag;}
else if(leftflag&&!rightflag){return leftflag;}
else{return NULL;}
完整代码
点击查看代码
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root){return NULL;}
if(root==p||root==q){return root;}
TreeNode*leftflag=lowestCommonAncestor(root->left,p,q);
TreeNode*rightflag=lowestCommonAncestor(root->right,p,q);
if(leftflag&&rightflag){return root;}
else if(!leftflag&&rightflag){return rightflag;}
else if(leftflag&&!rightflag){return leftflag;}
else{return NULL;}
}
};