面试必考精华版Leetcode236. 二叉树的最近公共祖先

题目：

代码(首刷看解析 10.1）：

class Solution {
public:
    TreeNode* ans=nullptr;
    bool FindSon(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root == nullptr)  return false;
        
        bool lson = FindSon(root->left,p,q);
        bool rson = FindSon(root->right,p,q);
        if( (lson&&rson) || ((root->val==p->val)||(root->val==q->val)) && (lson||rson) ){
              ans=root;
        }
        return  lson||rson||((root->val==p->val)||(root->val==q->val));
    }
 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        FindSon(root,p,q);
        return ans;
    }
};

        后续多做几遍

代码(二刷看解析 2024年1月31日）

class Solution {
private:
    TreeNode* x = nullptr;
    int count = 0;
public:
    bool Helper(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (!cur) return false;
 
        bool left = Helper(cur->left, p, q);
        bool right = Helper(cur->right, p, q);
   
        if ((left && right) || ((cur == p || cur == q) && (left || right))) {
            x = cur;
            return true;
        }
        return left || right || (cur == p || cur == q);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        Helper(root, p, q);
        return x;
    }
};

代码(三刷自解 2024年3月6日）

class Solution {
public:
    TreeNode* res;
    bool recursion(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return false;
        
        bool leftcheck = recursion(root->left, p, q);
        bool rightcheck = recursion(root->right, p, q);
 
        bool thisnode = false;
        if (root->val == q->val || root->val == p->val)
            thisnode = true;
 
        if ((leftcheck && rightcheck) || (leftcheck && thisnode) || (rightcheck && thisnode)) {
            res = root;
            return false;
        }
        return thisnode || leftcheck || rightcheck;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        res = nullptr;
        recursion(root, p, q);
        return res;
    }
};