二叉树
先前学习的数据结构中链表和数组均表示线性结构
然而现实世界十分复杂，怎么可能事物之间都是线性关系呢？
因此引入了树这种数据结构
树是一种用于描述层级关系的非线性数据结构，由若干节点组成，其中存在一个唯一的起点(根节点root)，其余节点通过父子关系组织起来，很好想象吧
先来看看最典型的树，二叉树，一种特殊的树结构，其中每个节点最多包含两个子节点
各种乱七八糟的定义先不管(自己问豆包qwq)
直观地理解一下
可以想到
二叉树的任意一个节点都可以被视为一棵更小的二叉树，问题往往可以通过递归算法拆解为当前节点+左子树的问题+右子树的问题，层层递归，直至没有节点
空讲有点抽象
首先来看看二叉树的三种遍历方式
用递归的方式应该很好理解…
94.二叉树的中序遍历
中序遍历: 左 -> 根 -> 右
前序遍历: 根 -> 左 -> 右
后序遍历: 左 -> 右 -> 根
递归
解：
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
|
class Solution {
public:
vector<int> res;
void dfs(TreeNode* root){
if(!root) return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
|
求解二叉树的最大深度也是同样的思路
104.二叉树的最大深度
递归
解：
1
2
3
4
5
6
7
| class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
|
后面简单做了一些题目加深理解…
226.翻转二叉树
解：
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->right = left;
root->left = right;
return root;
}
};
|
101.对称二叉树
解：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return isMirror(root->left,root->right);
}
bool isMirror(TreeNode* a,TreeNode* b){
if(!a && !b) return true;
if(!a || !b) return false;
if(a->val != b->val) return false;
return isMirror(a->left,b->right) && isMirror(a->right,b->left);
}
};
|
543.二叉树的直径
解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int ans = 0;
int depth(TreeNode* root){
if(!root) return 0;
int left = depth(root->left);
int right = depth(root->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return ans;
}
};
|
108.将有序数组转换为二叉搜索树
二叉搜索树 BST，引入了大小关系，定义是对于任意一个节点，其左子树中所有节点的值都小于该节点，而右子树中所有节点的值都大于该节点
传统数组or链表查找，需要循环遍历，时间复杂度为$O(n)$
而不难想到二叉搜索树是$O(\log n)$
可见其在查找这件事上的优越性，类似于二分的思想?
解：
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
TreeNode* build(vector<int>& nums, int l, int r){
if(l > r) return nullptr;
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, l, mid - 1);
root->right = build(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums,0,nums.size() - 1);
}
};
|
102.二叉树的层序遍历
要用到队列数据结构，其实我感觉队列和栈都挺好理解的，一个先进先出，一个后进先出罢了
解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(level);
}
return res;
}
};
|
二叉搜索树的插入,搜索与删除
递归实现
删除操作稍微麻烦一点，分类讨论即可
思考,思索…
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
|
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* insert(TreeNode* t, int val) {
if (t == NULL) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (val < t->data) {
t->left = insert(t->left, val);
} else if (val > t->data) {
t->right = insert(t->right, val);
}
return t;
}
int search(TreeNode* root, int key) {
if (root == NULL) return 0;
if (root->data == key) {
return 1;
} else if (root->data < key) {
return search(root->right, key);
} else {
return search(root->left, key);
}
}
TreeNode* findMin(TreeNode* node){
if(node == NULL) return NULL;
while(node->left != NULL){
node = node->left;
}
return node;
}
TreeNode* removeNode(TreeNode* root,int val){
if(root == NULL) return NULL;
if(root->data < val){
root->right = removeNode(root->right,val);
}else if(root->data > val){
root->left = removeNode(root->left,val);
}else{
if(root->left == NULL && root->right == NULL){
free(root);
return NULL;
}else if(root->left == NULL){
TreeNode* temp = root->right;
free(root);
return temp;
}else if(root->right == NULL){
TreeNode* temp = root->left;
free(root);
return temp;
}else{
TreeNode* minNode = findMin(root->right);
root->data = minNode->data;
root->right = removeNode(root->right,minNode->data);
}
}
return root;
}
|
可以看到BST的实现中存在一些问题
比如依次插入1,2,3,4,5
形成一个每个节点只有右子树的树
那和链表有什么区别!
因此引入了平衡二叉树
即控制树的高度以保证其各类操作的高效性
先来看看AVL树吧
其定义为
对于任意一个节点，其左子树和右子树的高度差(平衡因子)的绝对值不超过1，一旦某次插入或删除操作破坏了这一约束，树结构便会通过旋转(rotation)操作进行调整，以重新恢复平衡
旋转有左旋，右旋
其中又分为四种情况，LL,RR,LR,RL，依旧分类讨论+递归
来看看具体怎么实现吧
平衡二叉树之AVL树
旋转…
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
typedef struct TreeNode{
int data;
int height;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int height(TreeNode* node){
return node == NULL ? 0 : node->height;
}
int max(int a,int b){
return a > b ? a : b;
}
TreeNode* newNode(int val){
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = val;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
TreeNode* rightRotate(TreeNode* y){
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left),height(y->right)) + 1;
x->height = max(height(x->left),height(x->right)) + 1;
return x;
}
TreeNode* leftRotate(TreeNode* x){
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left),height(x->right)) + 1;
y->height = max(height(y->left),height(y->right)) + 1;
return y;
}
int getBalance(TreeNode* node){
if(node == NULL) return 0;
return height(node->left) - height(node->right);
}
TreeNode* insert(TreeNode* node,int val){
if(node == NULL) return newNode(val);
if(val < node->data){
node->left = insert(node->left,val);
}else if(val > node->data){
node->right = insert(node->right,val);
}else{
return node;
}
node->height = 1 + max(height(node->left),height(node->right));
int balance = getBalance(node);
if(balance > 1 && val < node->left->data){
return leftRotate(node);
}
if(balance < -1 && val > node->right->data){
return leftRotate(node);
}
if(balance > 1 && val > node->left->data){
node->left = leftRotate(node->left);
return rightRotate(node);
}
if(balance < -1 && val < node->right->data){
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
TreeNode* findMin(TreeNode* node){
while(node->left != NULL){
node = node->left;
}
return node;
}
TreeNode* deleteNode(TreeNode* root,int key){
if(root == NULL){
return root;
}
if(key < root->data){
root->left = deleteNode(root->left,key);
}else if(key > root->data){
root->right = deleteNode(root->right,key);
}else{
if(root->left == NULL || root->right == NULL){
TreeNode* temp = root->left ? root->left : root->right;
if(temp == NULL){
temp = root;
root = NULL;
}else{
*root = *temp;
}
free(temp);
}else{
TreeNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right,temp->data);
}
}
if(root == NULL) return root;
root->height = 1 + max(height(root->left),height(root->right));
int balance = getBalance(root);
if(balance > 1 && getBalance(root->left) >= 0){
return rightRotate(root);
}
if(balance < -1 && getBalance(root->right) <= 0){
return leftRotate(root);
}
if(balance > 1 && getBalance(root->left) < 0){
root->left = leftRotate(root->left);
return rightRotate(root);
}
if(balance < -1 && getBalance(root->right) > 0){
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
|
理解…
有点懵了?
没事儿
还有更难绷的
接下来登场的是
红黑树!!!
平衡二叉树之红黑树
逆天…
可以看到，AVL树的平衡条件过于严格，导致维护成本过高
不是在旋转，就是在旋转的路上…
因此又引入了红黑树
通过对节点标记为红色或黑色，并维护一组颜色规则，确保从任意节点到其后代叶子节点的路径上，黑色节点的数量保持一致，从而避免树结构发生严重退化
这种设计哲学在旋转次数,维护成本与查找效率之间，取得了一个极为实用的折中，因此在工程中十分讨喜
下面”简单”实现一下
旋转操作和AVL树倒是差不多
但是这个各种染色操作太逆天了
不过还是依照一定的逻辑来的
自己细品吧…
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
|
enum Color { RED, BLACK };
struct Node {
int key;
Color color;
Node *left, *right, *parent;
Node(int k)
: key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RBTree {
private:
Node* root;
Node* NIL;
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NIL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void rightRotate(Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != NIL)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NIL)
root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}
void insertFix(Node* z) {
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
void transplant(Node* u, Node* v) {
if (u->parent == NIL)
root = v;
else if (u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
v->parent = u->parent;
}
Node* minimum(Node* x) {
while (x->left != NIL)
x = x->left;
return x;
}
void deleteFix(Node* x) {
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node* w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
leftRotate(x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rightRotate(w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
Node* w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rightRotate(x->parent);
w = x->parent->left;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
leftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
public:
RBTree() {
NIL = new Node(0);
NIL->color = BLACK;
NIL->left = NIL->right = NIL;
NIL->parent = NIL;
root = NIL;
}
void insert(int key) {
Node* z = new Node(key);
z->left = z->right = NIL;
z->parent = NIL;
Node* y = NIL;
Node* x = root;
while (x != NIL) {
y = x;
x = (key < x->key) ? x->left : x->right;
}
z->parent = y;
if (y == NIL)
root = z;
else if (key < y->key)
y->left = z;
else
y->right = z;
z->color = RED;
insertFix(z);
}
void remove(int key) {
Node* z = root;
while (z != NIL && z->key != key) {
z = (key < z->key) ? z->left : z->right;
}
if (z == NIL)
return;
Node* y = z;
Color yColor = y->color;
Node* x;
if (z->left == NIL) {
x = z->right;
transplant(z, z->right);
} else if (z->right == NIL) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
yColor = y->color;
x = y->right;
if (y->parent != z) {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (yColor == BLACK)
deleteFix(x);
}
};
|
还有好多树啊…
慢慢来…
98.验证二叉搜索树
使用上下界递归:递归时传递当前节点允许的最小值和最大值，确保每个节点都在其祖先约束的范围内
解:
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
|
class Solution {
public:
bool isValidBST(TreeNode* root) {
return dfs(root, LONG_MIN, LONG_MAX);
}
bool dfs(TreeNode* node, long lower, long upper) {
if(!node) return true;
if(node->val >= upper || node->val <= lower) {
return false;
}
return dfs(node->left, lower, node->val) && dfs(node->right, node->val, upper);
}
};
|
230.二叉搜索树中第k小的元素
BST的中序遍历结果是升序序列，因此第k小的元素就是中序遍历的第k个节点
解:
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
|
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int res = 0;
inorder(root, k ,res);
return res;
}
void inorder(TreeNode* node, int& k, int& res) {
if(!node || k == 0) return;
inorder(node->left, k, res);
if(--k == 0) {
res = node->val;
return;
}
inorder(node->right, k, res);
}
};
|
199.二叉树的右视图
层序遍历即可
解:
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
|
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(!root) return res;
vector<vector<int>> whole;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
vector<int> level;
int n = q.size();
for(int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
whole.push_back(level);
}
int size = whole.size();
for(int i = 0; i < size; i++) {
res.push_back(whole[i].back());
}
return res;
}
};
|
114.二叉树展开为链表
我的思路:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<TreeNode*> res;
void dfs(TreeNode* root) {
if (!root) return;
res.push_back(root);
dfs(root->left);
dfs(root->right);
}
void flatten(TreeNode* root) {
if (!root)
return;
dfs(root);
for (int i = 1; i < res.size(); i++) {
res[i - 1]->left = nullptr;
res[i - 1]->right = res[i];
}
}
};
|
ai的优雅解法:
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
TreeNode* prev = nullptr;
void flatten(TreeNode* root) {
if(!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = nullptr;
prev = root;
}
};
|
nb!
学到了
105.从前序与中序遍历序列构造二叉树
没想出来qwq
答案思路:
preorder的第一个元素必然是root，在inorder中找到其值对应的索引
inorder中该值左边的序列即root左子树的中序遍历，右边的序列即root右子树的中序遍历
记其左边的序列有n个元素
同理，preorder中第一个元素(root)后的n个元素构成的序列即为其左子树的前序遍历，剩余的元素构成的序列则为其右子树的前序遍历
随后递归即可
同时注意一下递归的结束条件
nb!
解:
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
| class Solution {
public:
unordered_map<int, int> pos;
TreeNode* build(vector<int>& preorder, int preL, int preR, vector<int>& inorder, int inL, int inR) {
if(preL > preR) return nullptr;
int rootVal = preorder[preL];
TreeNode* root = new TreeNode(rootVal);
int k = pos[rootVal];
int leftSize = k - inL;
root->left = build(preorder, preL + 1, preL + leftSize, inorder, inL, k - 1);
root->right = build(preorder, preL + 1 + leftSize, preR, inorder, k + 1, inR);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for(int i = 0; i < n; i++) {
pos[inorder[i]] = i;
}
return build(preorder, 0, n - 1, inorder, 0, n - 1);
}
};
|
437.路径总和 III
我的暴力解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
if(!root) return 0;
return countFrom(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
int countFrom(TreeNode* node, long long targetSum) {
if(!node) return 0;
int count = 0;
if(node->val == targetSum) count++;
count += countFrom(node->left, targetSum - node->val);
count += countFrom(node->right, targetSum - node->val);
return count;
}
};
|
ai展示最优解:
前缀和HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> prefixCount;
prefixCount[0] = 1;
return dfs(root, 0, targetSum, prefixCount);
}
int dfs(TreeNode* node, long long currSum, int target, unordered_map<long long, int>& prefixCount) {
if(!node) return 0;
currSum += node->val;
int count = 0;
if(prefixCount.count(currSum - target)) {
count += prefixCount[currSum - target];
}
prefixCount[currSum]++;
count += dfs(node->left, currSum, target, prefixCount);
count += dfs(node->right, currSum, target, prefixCount);
prefixCount[currSum]--;
return count;
}
};
|
236.二叉树的最近公共祖先
解:
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || 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;
return left ? left : right;
}
};
|
124.二叉树中的最大路径和
解:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maxSum = INT_MIN;
int dfs(TreeNode* root) {
if(!root) return 0;
int left = max(dfs(root->left), 0);
int right = max(dfs(root->right), 0);
maxSum = max(maxSum, root->val + left + right);
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return maxSum;
}
};
|