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

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;
    }
};

递归、回溯