Leetcode236.二叉树的最近公共祖先(HOT100)

链接

代码：

class Solution {
public:
    TreeNode* ans = nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ans;//dfs方法会把答案写在ans中我们返回即可
    }
    int dfs(TreeNode* root,TreeNode* p,TreeNode*q){
        if(root==nullptr){
            return 0;
        }
        //我们使用state的低两位表示 p q是否有找到，比如00代表都没有找到，10代表q找到了，p没有找到
        int state = dfs(root->left,p,q);//遍历左子树找pq
        if(root==p)state|=1;//然后再看根节点
        else if(root==q)state|=2;
        state|=dfs(root->right,p,q);//然后再看右子树
        if(state==3&&ans==nullptr){//如果是3，还不能盲目更新，要看之前是否有更新过，dfs是从底层上来的，如果之前更新过，现在就不要更新了
            ans = root;
        }
        return state;
    }
};
https://www.acwing.com/video/1620/

代码二：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root||root==p||root==q){
            return root;
        }
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);
        if(left&&right){
            return root;
        }
        if(left){
            return left;
        }
        if(right){
            return right;
        }
        return nullptr;
    }
};


https://www.bilibili.com/video/BV19t411w7Ep?t=3436.9

原文地址：https://blog.csdn.net/kitesxian/article/details/143863332

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！