108、【树与二叉树】leetcode ——235. 二叉搜索树的最近公共祖先:普通树解法+BST性质解法(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:235. 二叉搜索树的最近公共祖先
解题思路
1、普通树找公共祖先解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root ==q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
if(left && !right) return left;
return right;
}
};
2、利用BST性质解法
递归法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return NULL;
// 当p和q都在左侧时,向左遍历
if(root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}
// 当p和q都在右侧时,向右遍历
if(root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
}
// 当p和q分别在两侧时,第一个找到的这种结点一定为LCA
return root;
}
};
迭代法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root) {
int value = root->val;
if(value > p->val && value > q->val) root = root->left;
else if(value < p->val && value < q->val) root = root->right;
else return root;
}
return NULL;
}
};
参考文章:235. 二叉搜索树的最近公共祖先
相关文章
- 关于c++ 感想
- Python 零基础快速上手(与C/C++对比)
- C/C++每日一练(20230224)
- C语言/C++基础之弹力豆腐串
- C语言/C++常见习题问答集锦[八十二]之数据结构顺序表
- Open3D(C++) 获取点云坐标最值
- atitit。gui 界面皮肤以及换肤总结 java .net c++
- 在Qt(C++)中使用QThread实现多线程
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- C++设计模式之状态模式
- Leetcode 搜索旋转排序数组(执行用时: 0 ms , 在所有 C++ 提交中击败了 100.00% 的用户)
- LeetCode 整数转罗马数字(执行用时: 12 ms , 在所有 C++ 提交中击败了 32.38% 的用户)
- Leetcode 两数之和 C / C++
- C++ 修改外部类简单测试
- C++暴力枚举vector所有连续子序列
- c++ 常量与类常量
- c++ vector C++ vector存放结构体 并且排序
- 下了个C-Free,结果点新建,出来的就是.cpp 怎么变成.c呢。。。他默认新建文件是c++的啊,
- C++ 反汇编:分析类的实现原理
- 【C++设计模式】创建型模式 — 单例模式
- C++之Singleton单例和单例模板类讲解
- C++标准里 string和wstring