Node 的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
|
一些比较 trick 的问题
删除 List 中的一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool delete_node(ListNode* curr)
{
if(curr->next)
{
curr->val = curr->next->val;
curr->next = curr->next->next;
return true;
}
else
{
return false;
}
}
|
将二叉树转化为双向链表
@算法示意图
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
|
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == NULL) return pRootOfTree;
pRootOfTree = ConvertNode(pRootOfTree);
while(pRootOfTree->left) pRootOfTree = pRootOfTree->left;
return pRootOfTree;
}
TreeNode* ConvertNode(TreeNode* root)
{
if(root == NULL) return root;
if(root->left)
{
TreeNode *left = ConvertNode(root->left);
while(left->right) left = left->right;
left->right = root;
root->left = left;
}
if(root->right)
{
TreeNode *right = ConvertNode(root->right);
while(right->left) right = right->left;
right->left = root;
root->right = right;
}
return root;
}
};
|
从链表中查找倒数 Kth 个
本题的思路就是通过两个指针，一个快一个慢，中间相差 k 个，当其中快指针指向结尾的时候，慢指针指向的位置就是所求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* fast = pListHead;
int i = k;
while(fast && i > 0)
{
fast = fast->next;
i--;
}
if(i != 0) return NULL;
ListNode* slow = pListHead;
while(fast && slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
|
红黑树
https://blog.csdn.net/weewqrer/article/details/51866488
用途
红黑树和 AVL 树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。对于查找、插入、删除、最大、最小等动态操作的时间复杂度为 O (lgn). 常见的用途有以下几种：
STL（标准模板库）中在 set map 是基于红黑树实现的。
Java 中在 TreeMap 使用的也是红黑树。
epoll 在内核中的实现，用红黑树管理事件块。 linux 进程调度 Completely Fair
Scheduler, 用红黑树管理进程控制块
红黑树 VS AVL 树
常见的平衡树有红黑树和 AVL 平衡树，为什么 STL 和 linux 都使用红黑树作为平衡树的实现？大概有以下几个原因：
从实现细节上来讲，如果插入一个结点引起了树的不平衡，AVL 树和红黑树都最多需要 2 次旋转操作，即两者都是 O (1)；但是在删除 node 引起树的不平衡时，最坏情况下，AVL 需要维护从被删 node 到 root 这条路径上所有 node 的平衡性，因此需要旋转的量级 O (logN)，而 RB-Tree 最多只需 3 次旋转，只需要 O (1) 的复杂度
从两种平衡树对平衡的要求来讲，AVL 的结构相较 RB-Tree 来说更为平衡，在插入和删除 node 更容易引起 Tree 的 unbalance，因此在大量数据需要插入或者删除时，AVL 需要 rebalance 的频率会更高。因此，RB-Tree 在需要大量插入和删除 node 的场景下，效率更高。自然，由于 AVL 高度平衡，因此 AVL 的 search 效率更高。
总体来说，RB-tree 的统计性能是高于 AVL 的
参考链接
[1]. 关于红黑树的介绍
预览: