【打卡】牛客网：BM38 在二叉树中找到两个节点的最近公共祖先

资料：

非常重要的小细节！ 

在C++类中vector声明，报错 “expected parameter declarator”_c++ vector报错-CSDN博客

自己写的：

1.（没有深度思考）能通过5/10，原因：内存受限。

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
 
    // 不能是bool型，还得是返回vector型
    // 因为当递归返回后，path的元素会减少的，不像全局变量那样只push_back
    vector<int> getPath(TreeNode* root, int target, vector<int> path) {
        path.push_back(root->val);
        vector<int> a;
        if (root == NULL)
            return a;
            
        if (root->val == target)
            return path;
 
        if (root->left != NULL){
            a = getPath(root->left, target, path); 
            if (!a.empty())
                return a;
        }
        if (root->right != NULL)
            a = getPath(root->right, target, path);
        
        return a;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int> path1; // 声明了一个int数组，大小没有指定
        vector<int> path2;
        path1 = getPath(root, o1, path1);
        path2 = getPath(root, o2, path2);
 
        int res;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1[i] == path2[i])
                res = path1[i];
            else
                break;
        }
        return res;
 
    }
};

疑问：①必须得返回，不能写成：

getPath(root->left, target, path); 
getPath(root->right, target, path);

②必须判断左右节点是否为空，不能写成：

a = getPath(root->left, target, path);

if (!a.empty())
        return a;
a = getPath(root->right, target, path); 
return a;

2.主要思想是用到全局变量。（主要是忘记dfs的模板了，即忘记了&的作用）

有一些编程细节，放在注释里面了。

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
 
    // vector flag={0,0};  // vector flag(2)为什么不行？
    int flag1 = 0;
    int flag2 = 0;
    vector<int> path1;
    vector<int> path2;
 
    void getPath1(TreeNode* root, int target) {
        if (root == NULL)
            return;
 
        if (root->val == target) {
            flag1 = 1;
            path1.push_back(root->val);
            return;
        }
 
        if (flag1 == 0)
            getPath1(root->left, target);
        if (flag1 == 0)
            getPath1(root->right, target);
 
        if (flag1 == 1)
            path1.push_back(root->val);
        return;
    }
    void getPath2(TreeNode* root, int target) {
        if (root == NULL)
            return;
 
        if (root->val == target) {
            flag2 = 1;
            path2.push_back(root->val);
            return;
        }
 
        if (flag2 == 0)
            getPath2(root->left, target);
        if (flag2 == 0)
            getPath2(root->right, target);
 
        if (flag2 == 1)
            path2.push_back(root->val);
        return;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        getPath1(root, o1);
        getPath2(root, o2);
 
        int res;
        // 这种方法不可以，path必须顺着来，不能逆着来。
        // for (int i = 0; i < path1.size() && i < path2.size(); i++) {
        //     if (path1[i] == path2[i]){
        //         res = path1[i];
        //         break;
        //     }
        // }
 
        reverse(path1.begin(), path1.end());
        reverse(path2.begin(), path2.end());
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1[i] == path2[i])
                res = path1[i];
            else
                break;
        }
 
        return res;  //必须在最后要return一下，不能只在for循环里return。
    }
};

模板的：

回溯！忘记了。

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
 
    // vector flag={0,0};  // vector flag(2)为什么不行？
    int flag = 0;
 
    void getPath(TreeNode* root, int target, vector<int>& path) {
        //忘记&的作用了
        if (flag == 1)
            return;
        if (root == NULL)
            return;
 
        path.push_back(root->val);
 
        if (root->val == target) {
            flag = 1;
            return;
        }
 
        getPath(root->left, target, path);
        getPath(root->right, target, path);
 
        if(flag == 1) // 找到了，就不需要pop
            return;
        path.pop_back();
    }
 
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int> path1, path2;
        getPath(root, o1, path1);
        flag = 0;
        getPath(root, o2, path2);
 
        int res;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1[i] == path2[i])
                res = path1[i];
            else
                break;
        }
        return res;
    }
};