本文介绍: 二叉搜索树专题again,包括插入,删除节点,递归迭代都可以解决,感觉有时候迭代挺简单的。
235. 二叉搜索树的最近公共祖先
普通二叉树的最近公共祖先方法通用,但是涉及到二叉排序树的特性,就需要记得遍历得到的最近的一个值在p q值之间的结点,这个就是目标的公共祖先结点。这题算是写的比较透的了,用了三种方法。
class Solution {
public:
TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){
// 1、以下是普通搜索树的方法
// if (root == nullptr || root == p || root == q) return root;
// TreeNode* left = traversal(root->left, p, q);
// TreeNode* right = traversal(root->right, p, q);
// if (left && right) return root;
// else if (!left && right) return right;
// else if (left && !right) return left;
// else return nullptr;
// 2、以下是用了二叉搜索树特性的方法
if (root == nullptr) return root;
// 并不是每次都遍历左右,而是视情况而定
if (root->val > p->val && root->val > q->val){
// 当前值大于两个目标值,则向左遍历
TreeNode* left = traversal(root->left, p ,q);
// 相当于把找到的值一直传上去
if (left != nullptr){
return left;
}
}
if (root->val < p->val && root->val < q->val){
// 当前值小于两个目标值,则向右遍历
TreeNode* right = traversal(root->right, p ,q);
if (right != nullptr){
return right;
}
}
// 两种情况都不符合,不递归了,直接返回当前节点,这个是最先找到的祖先节点
return root;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// return traversal(root, p, q);
// 3、迭代写法
TreeNode* cur = root;
while (cur != nullptr){
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 nullptr;
}
};
考研的时候我记得好像就背过如何建一棵排序二叉树,当时就觉得好简单,现在看也简单的,但是不容易写出来。递归写法最重要的就是利用回溯的特点,用上一层的结点接住下一层的返回值,二分查找得到的空节点就可以返回一个新建的结点。迭代写法需要用一个父节点记录找到的插入位置的父节点,从而用父节点接着新建结点。
class Solution {
public:
TreeNode* traversal(TreeNode* root, int val){
// 按照二叉搜索树的特性遍历二叉树,如果遇到空节点就是要插入的结点,返回新建的节点
if (root == nullptr){
TreeNode* node = new TreeNode(val);
return node;
}
// 用root的孩子接住返回的结点
if (root->val > val) root->left = traversal(root->left, val);
if (root->val < val) root->right = traversal(root->right, val);
return root;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 1、迭代法
// if (root == nullptr){
// TreeNode* node = new TreeNode(val);
// return node;
// }
// null不是特定节点,因此不可记录位置,需要用一个父节点记录要插入位置的前一个节点
// TreeNode* pre = root;
// TreeNode* cur = root;
// while (cur != nullptr){
// pre = cur;
// if (val > cur->val){
// cur = cur->right;
// }
// else if (val < cur->val){
// cur = cur->left;
// }
// }
// TreeNode* node = new TreeNode(val);
// if (val < pre->val){
// pre->left = node;
// }
// else if (val > pre->val){
// pre->right = node;
// }
// return root;
//
return traversal(root, val);
}
};
450. 删除二叉搜索树中的节点
这题更是重量级,如果没写过真的很难写出来。包括现在我也云里雾里的,感觉可以算是hard题了。因为删除需要考虑的状况有点多,所以情况也复杂一些。当然我觉得用迭代会更简单点,但是现在不想深究它了。二刷再来掌握。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key){
if (root->left == nullptr && root->right == nullptr){
delete root;
return nullptr;
}
else if (root->left == nullptr){
auto retNode = root->right;
delete root;
return retNode;
}
else if (root->right == nullptr){
auto retNode = root->left;
delete root;
return retNode;
}
else {
TreeNode* cur = root->right;
while (cur->left != nullptr){
cur = cur->left;
}
cur->left = root->left;
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
原文地址:https://blog.csdn.net/m0_46304590/article/details/135963880
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_65841.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。