题解 | #在二叉树中找到两个节点的最近公共祖先#

在二叉树中找到两个节点的最近公共祖先

https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

class Solution {
  public:
    vector<int> vc1;
    vector<int> vc2;
    bool find1 = false;
    bool find2 = false;
    int common = -1;
    void GetS(TreeNode* root, int o1, int o2) {
        if (common >= 0)
            return;
        if (!root) {
            if (find1 && find2) {
                for (int i = 0; i < vc1.size() && i < vc2.size(); i++) {
                    if (vc1[i] == vc2[i])
                        common = vc1[i];
                    else
                        return;
                }
            }
            return;
        }
        if (find1 && find2) {
            for (int i = 0; i < vc1.size() && i < vc2.size(); i++) {
                if (vc1[i] == vc2[i])
                    common = vc1[i];
                else
                    break;
            }
        } else if (find1) {
            vc2.push_back(root->val);
            if (root->val == o2) {
                find2 = true;
            }
            GetS(root->left, o1, o2);
            GetS(root->right, o1, o2);
            if (!find2)
                vc2.pop_back();
        } else if (find2) {
            vc1.push_back(root->val);
            if (root->val == o1) {
                find1 = true;
            }
            GetS(root->left, o1, o2);
            GetS(root->right, o1, o2);
            if (!find1)
                vc1.pop_back();
        } else {
            vc1.push_back(root->val);
            if (root->val == o1) {
                find1 = true;
            }
            vc2.push_back(root->val);
            if (root->val == o2) {
                find2 = true;
            }
            GetS(root->left, o1, o2);
            GetS(root->right, o1, o2);
            if (!find1)
                vc1.pop_back();
            if (!find2)
                vc2.pop_back();
        }
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        GetS(root, o1, o2);
        return common;
    }
};

递归、回溯

全部评论

相关推荐

07-22 11:07
门头沟学院 Java
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务