1、235二叉搜索树的最近公共祖先
二叉搜索树特性：中序遍历是单调序列。
对于二叉搜索树，左树小于root，右树大于root。给定两个节点p和q，如果p小于root,q大于root，pq一定位于root的两边（两棵子树）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return root;
if(p->val <= root->val && q->val >= root->val)return root;
if(p->val >= root->val && q->val <= root->val)return root;
if(p->val < root->val && p->val < root->val){
return lowestCommonAncestor(root->left,p,q);
}
if(p->val > root->val && p->val > root->val){
return lowestCommonAncestor(root->right,p,q);
}
return nullptr;
}
};
class Solution {
private:
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
if (cur == NULL) return cur;
if (cur->val > p->val && cur->val > q->val) {
TreeNode* left = traversal(cur->left, p, q);
if (left != NULL) {
return left;
}
}
if (cur->val < p->val && cur->val < q->val) {
TreeNode* right = traversal(cur->right, p, q);
if (right != NULL) {
return right;
}
}
return cur;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
};
|
2、701二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
我的思路： 一开始没想出来。看了代码随想录就会了。
这里提供两种思路，第一种在局部重构，第二种比较推荐，递归遍历找到空节点就加上。
代码随想录：用的构造二叉树的那个框架。思路更清晰。推荐。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
void traverse(TreeNode* root, int val) {
if(val < root->val){
if(root->left == nullptr)root->left = new TreeNode(val);
else traverse(root->left,val);
}
if(val > root->val){
if(root->right == nullptr)root->right = new TreeNode(val);
else traverse(root->right,val);
}
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == nullptr)return new TreeNode(val);;
traverse(root,val);
return root;
}
};
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
|
3、450删除二叉搜索树中的节点
我的思路：没做出来。看了代码随想录后我写了，思路是先递归找到需要删除节点key的父节点，然后把key的1子树接上，2子树再递归接在1上。思路比较复杂。
代码随想录：依然使用构造二叉树的框架去删除节点。整体逻辑清晰很多。有一个关键点，由于右子树一定大于左子树，那么右子树一定接在左子树的右侧第一个nullptr上。反过来同理。这省去查找的麻烦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
class Solution {
public:
void traverse2(TreeNode* root,TreeNode* insert){
if(insert == nullptr)return;
if(insert->val < root->val){
if(root->left == nullptr){
root->left = insert;
return;
}else{
traverse2(root->left,insert);
}
}
if(insert->val > root->val){
if(root->right == nullptr){
root->right = insert;
return;
}else{
traverse2(root->right,insert);
}
}
}
void traverse(TreeNode* root, int val){
if(root->left == nullptr && root->right == nullptr) return;
if(root->left != nullptr && root->left->val == val){
auto temp = root->left->right;
if(root->left->left!=nullptr){
root->left = root->left->left;
traverse2(root->left,temp);
}else{
root->left = root->left->right;
}
return;
}
if(root->right != nullptr && root->right->val == val){
auto temp = root->right->right;
if(root->right->left!=nullptr){
root->right = root->right->left;
traverse2(root->right,temp);
}else{
root->right = root->right->right;
}
return;
}
if(val < root->val)traverse(root->left,val);
if(val > root->val)traverse(root->right,val);
}
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == nullptr)return root;
if(root->val == key){
if(root->left != nullptr){
traverse2(root->left,root->right);
return root->left;
}
if(root->right != nullptr){
traverse2(root->right,root->left);
return root->right;
}
if(root->left == nullptr && root->right == nullptr){
return nullptr;
}
}
traverse(root,key);
return root;
}
};
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)return nullptr;
if(root->left!=nullptr && root->right==nullptr)return root->left;
if(root->left==nullptr && root->right!=nullptr)return root->right;
if(root->left!=nullptr && root->right!=nullptr){
auto temp = root->left;
while(temp->right)temp = temp->right;
temp->right = root->right;
return root->left;
}
}
root->left = deleteNode(root->left,key);
root->right = deleteNode(root->right,key);
return root;
}
};
|
代码随想录算法训练第二十天|235二叉搜索树的最近公共祖先|701二叉搜索树中的插入操作|450删除二叉搜索树中的节点
