class Solution {
public:
bool found = false;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)return NULL;
TreeNode*l = lowestCommonAncestor(root->left, p, q);
TreeNode*r = lowestCommonAncestor(root->right, p, q);
if(s1(root,l,r,p,q)){
return root;
}else if(s2(root,l,r,p,q)){
if(found){
if(l!=NULL)return l;
else return r;
}else return root;
}else if(s3(root,l,r,p,q)){
return NULL;
}else{
found = true;
return root;
}
}
bool fdi(TreeNode *a, TreeNode*b,TreeNode*c){
return a->val==b->val||a->val==c->val;
}
bool s1(TreeNode* root,TreeNode*l,TreeNode*r,TreeNode*p,TreeNode*q){
return fdi(root,p,q)&&l==NULL&&r==NULL;
}
bool s2(TreeNode* root,TreeNode*l,TreeNode*r,TreeNode*p,TreeNode*q){
return (!fdi(root,p,q))&&((l==NULL)^(r==NULL));
}
bool s3(TreeNode* root,TreeNode*l,TreeNode*r,TreeNode*p,TreeNode*q){
return (!fdi(root,p,q))&&l==NULL&&r==NULL;
}
};
后序遍历,处理结点时根据跟、左右儿子的8个状态返回对应值(1表示找到,0表示没找到)
(左到右:根,左,右)
s1 1 0 0;
s2 0 1 0;0 0 1;
s3 0 0 0;
s4 1 1 0;0 1 1;1 0 1;
s1表示根节点是,左右儿子不是,返回根
s3表示都不是,返回NULL
s4一定表示找到了答案,三种情况都返回根,并更新状态值found为true
s2有两种情况,如果已经找到了,则左右哪个不为NULL哪个就为答案,如果没找到则答案一定需要以当前root为后代,返回root
结点分情况处理,非常非常麻烦,但是思路很清晰。