C++ 解法, 执行用时: 4ms, 内存消耗: 980KB, 提交时间: 2022-02-08
/**
* 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整型
*/
TreeNode findNode(TreeNode* root,int p,int q){
if(!root){
return *root;
}
if(root->val==p || root->val==q){
return *root;
}
if(p<root->val && q<root->val){
return findNode(root->left, p, q);
}else if(p>root->val && q>root->val){
return findNode(root->right, p, q);
}else{
return *root;
}
}
int lowestCommonAncestor(TreeNode* root, int p, int q) {
return findNode(root, p, q).val;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1020KB, 提交时间: 2022-02-08
/**
* 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 here
if (root == nullptr) {
return -1;
}
if (p>q){
int temp = q;
q=p;
p=q;
}
return lowest(root,p,q);
}
int lowest(TreeNode* root, int p, int q) {
if (root == nullptr) {
return -1;
}
if (root->val >q){
return lowest(root->left, p, q);
}
if (root->val < p){
return lowest(root->right, p, q);
}
return root->val;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1020KB, 提交时间: 2021-11-21
/**
* 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整型
*/
void findTargetNode(TreeNode* root, vector<int>& path, int target) {
if (!root) return;
if (root->val == target) {
// 找到了
path.push_back(root->val);
return;
}
else if (root->val > target) {
// 在左子树搜索
path.push_back(root->val);
findTargetNode(root->left, path, target);
if (path.back() == target) return;
path.pop_back();
}
else {
// 在右子树搜索
path.push_back(root->val);
findTargetNode(root->right, path, target);
if (path.back() == target) return;
path.pop_back();
}
}
int lowestCommonAncestor(TreeNode* root, int p, int q) {
vector<int> path1;
findTargetNode(root, path1, p);
vector<int> path2;
findTargetNode(root, path2, q);
if (path1.size() == 0 || path2.size() == 0) return -1;
int l = 0;
while (l < path1.size() && l < path2.size() && path1[l] == path2[l]) {
l++;
}
return path1[l - 1];
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1032KB, 提交时间: 2021-11-21
/**
* 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 ret=0;
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if(root==nullptr)
return -1;
if((p>=root->val && q<=root->val) || p<=root->val && q>=root->val)
ret=root->val;
else if(p<=root->val && q<=root->val){
ret=lowestCommonAncestor(root->left,p,q);
}else
ret=lowestCommonAncestor(root->right,p,q);
return ret;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1032KB, 提交时间: 2021-11-17
/**
* 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 here
TreeNode* resNode=root;
while(1)
{
if(resNode->val<p && resNode->val <p)//当前节点比两个节点都小
{
resNode=resNode->right;
}else if(resNode->val >p && resNode->val>q)
{
resNode=resNode->left;
}else
break;
}
return resNode->val;
}
};
