【打卡】牛客网：BM37 二叉搜索树的最近公共祖先

自己写的：

感觉写的很工整。

/*** 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 p int整型 * @param q int整型 * @return int整型*/int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code hereif(p > q){int temp = p;p = q;q = temp;           }if(p <= root->val && q >= root->val) // p、q是不同节点return root->val;else if (q < root->val)return lowestCommonAncestor(root->left, p ,q);elsereturn lowestCommonAncestor(root->right, p ,q);}
};

模板的：

空间复杂度增加。用到了“记录搜索的路径”的方法，这可能是以后针对复杂问题也能用的、比较常用的模板吧。

/*** 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 p int整型 * @param q int整型 * @return int整型*/vector<int> getPath(TreeNode* root, int target){vector<int> path;while(root->val != target){path.push_back(root->val);if(root->val < target)root = root->right;elseroot = root->left;}path.push_back(root->val);return path;}int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code herevector<int> path1 = getPath(root, p);vector<int> path2 = getPath(root, q);int res;for(int i = 0; i < path1.size() && i < path2.size(); i++){if(path1[i] == path2[i])res = path1[i];elsebreak;}return res;}
};

【打卡】牛客网：BM37 二叉搜索树的最近公共祖先

自己写的：

感觉写的很工整。

/*** 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 p int整型 * @param q int整型 * @return int整型*/int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code hereif(p > q){int temp = p;p = q;q = temp;           }if(p <= root->val && q >= root->val) // p、q是不同节点return root->val;else if (q < root->val)return lowestCommonAncestor(root->left, p ,q);elsereturn lowestCommonAncestor(root->right, p ,q);}
};

模板的：

空间复杂度增加。用到了“记录搜索的路径”的方法，这可能是以后针对复杂问题也能用的、比较常用的模板吧。

/*** 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 p int整型 * @param q int整型 * @return int整型*/vector<int> getPath(TreeNode* root, int target){vector<int> path;while(root->val != target){path.push_back(root->val);if(root->val < target)root = root->right;elseroot = root->left;}path.push_back(root->val);return path;}int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code herevector<int> path1 = getPath(root, p);vector<int> path2 = getPath(root, q);int res;for(int i = 0; i < path1.size() && i < path2.size(); i++){if(path1[i] == path2[i])res = path1[i];elsebreak;}return res;}
};