day22
235.二叉搜索树的最近公共祖先
题目链接:235. 二叉搜索树的最近公共祖先
解题思路:参考
第一种:直接使用之前的普通二叉树找最近公共祖先的方法,自底向上
第二种:参考二叉树的性质,采用递归法,如果当前节点比p,q都要大,则向左遍历,如果当前节点比p,q都要小,向右遍历,否则直接返回当前节点
第三种:直接用循环,也是使用二叉树的性质
// 下面给出了三种代码
/**
* 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:
// 1.直接计算
// // 1.确定递归函数参数和返回值
// TreeNode* traversal(TreeNode* node,TreeNode* p,TreeNode* q){
// // 2.确定终止条件
// if( node == NULL ) return node;
// if( node == p || node == q) return node;
// // 3.确定单层递归逻辑
// // 自底向上,采用后续遍历,左右中
// TreeNode* left = traversal( node->left, p, q);
// TreeNode* right = traversal( node->right, p, q);
// // 中
// if( left != NULL && right != NULL ) return node; //左右不为空向上返回node
// else if( left != NULL && right == NULL) return left;
// else if( left == NULL && right != NULL) return right;
// else{ return NULL; }
// }
// 2.结合搜索二叉树的性质
TreeNode* traversal(TreeNode* cur,TreeNode* p,TreeNode* q){
// // 终止条件
// if ( cur == NULL ) return NULL;
// // 单层逻辑
// if ( cur->val > p->val && cur->val > q->val ){
// TreeNode* left = traversal( cur->left, p, q);
// if( left != NULL ) return left;
// }
// else if( cur->val < p->val && cur->val < q->val){
// TreeNode* right = traversal( cur->right, p, q);
// if( right != NULL ) return right;
// }
// return cur;
// 3.迭代法
while(cur){
if ( cur->val > p->val && cur->val > q->val ){
cur = cur->left;
}
else if( cur->val < p->val && cur->val < q->val){
cur = cur->right;
}
else { return cur;}
}
return NULL;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal( root, p, q);
}
};
701.二叉搜索树中的插入操作
题目链接:701. 二叉搜索树中的插入操作
通过递归方法,判断进来的元素是大于还是小于cur节点,最后将该元素插入末尾,注意代码的实现细节
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归插入节点
TreeNode* insert( TreeNode* node,int val){
// 确定终止条件
if ( node == NULL ){
TreeNode* result = new TreeNode(val);
return result;
}
if( node->val > val ) node->left = insert( node->left ,val); //必须用node->left来接住它,相当于插入left那边了
if( node->val < val ) node->right = insert( node->right , val); //用right接住它
return node;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
return insert( root,val);
}
};
450.删除二叉搜索树中的节点
题目链接:450. 删除二叉搜索树中的节点
删除节点需要改变树结构,分为以下五种情况
1.没找到删除的点
2.叶子节点,左空右空
3.左不空右空
4.左空右不空
5.左不空右不空:右子树继位,然后放在右子树中次小于删除节点的后面
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 确定递归返回值和参数
TreeNode* deleteT(TreeNode* node,int val){
// 确定终止条件
if( node == NULL ) return NULL; // 1.没找到删除的点
if ( node->val == val){
// 2.叶子节点 左空右空
if ( node->left == NULL && node->right == NULL ){ //返回空即删除该节点
delete node; //释放内存
return NULL;
}
// 第二种情况 左空右不空
else if ( node->left ==NULL && node->right != NULL){ //右节点直接指向其父节点
delete node; //释放内存
return node->right;
}
// 第三种情况 左不空右空
else if( node->left != NULL && node->right == NULL ){ //左节点直接指向其父节点
delete node; //释放内存
return node->left;
}
// 左不空右不空 将右子树继位,放在右子树中的最左边,也就是次小于删除节点的地方
else{
TreeNode* cur = node->right; //将右边提上去
while(cur->left != NULL ){
cur = cur->left;
}
cur->left = node->left; // 右子树的左节点
TreeNode* tmp = node; // 删除节点,清空内存
node = node->right;
delete tmp;
return node;
}
}
// 单层递归逻辑
if( node->val < val ) node->right = deleteT( node->right,val);
if( node->val > val ) node->left = deleteT( node->left,val);
return node;
}
TreeNode* deleteNode(TreeNode* root, int key) {
return deleteT( root,key);
}
};