食无求饱,居无求安,敏于事而慎于言.

0%

Zookeeper之Leader选举过程

Leader在集群中是一个非常重要的角色,负责了整个事务的处理和调度,保证分布式数据一致性的关键所在。既然Leader在ZooKeeper集群中这么重要所以一定要保证集群在任何时候都有且仅有一个Leader存在。

概念

Zookeeper Server三种角色:Leader,Follower,Observer。

Leader是Zookeeper 集群工作机制的核心,主要工作:

  • a.调度者:集群内部各个服务节点的调度者
  • b.事务请求:事务请求的唯一调度和处理者,保证集群事务处理的顺序性

Follower主要职责:

  • a.非事务请求:Follower 直接处理非事务请求,对于事务请求,转发给 Leader
  • b.Proposal 投票:Leader 上执行事务时,需要 Follower 投票,Leader 才真正执行
  • c.Leader 选举投票

Observer主要职责:

  • a.非事务请求:Follower 直接处理非事务请求,对于事务请求,转发给 Leader

Observer 跟 Follower的区别:

  • a.Follower 参与投票:Leader 选举、Proposal 提议投票(事务执行确认)
  • b.Observer 不参与投票:只用于提供非事务请求的处理

Zookeeper Server的状态

  • LOOKING:寻找Leader
  • LEADING:Leader状态,对应的节点为Leader。
  • FOLLOWING:Follower状态,对应的节点为Follower。
  • OBSERVING:Observer状态,对应节点为Observer,该节点不参与Leader选举。

其它概念

  • ZXID(zookeeper transaction id):每个改变Zookeeper状态的操作都会形成一个对应的zxid,并记录到transaction log中。 这个值越大,表示更新越新
  • myid:服务器SID,一个数字,通过配置文件配置,唯一
  • SID:服务器的唯一标识
  • 成为Leader的必要条件: Leader要具有最高的zxid;当集群的规模是n时,集群中大多数的机器(至少n/2+1)得到响应并follow选出的Leader。
  • 心跳机制:Leader与Follower利用PING来感知对方的是否存活,当Leader无法相应PING时,将重新发起Leader选举。

选举有两种情况,一是服务器启动的投票,二是运行期间的投票。

服务器启动时期的Leader选举

1.每个服务器发送一个投票(SID,ZXID)

其中sid是自己的myid,初始阶段都将自己投为Leader。

2.接收来自其他服务器的投票。

集群的每个服务器收到投票后,首先判断该投票的有效性,如检查是否是本轮投票、是否来自LOOKING状态的服务器。

3.处理投票

针对每个投票都按以下规则与自己的投票PK,PK后依据情况是否更新投票,再发送给其他机器。

  • a.优先检查ZXID,ZXID较大者优先为Leader
  • b.如果ZXID相同,检查SID,SID较大者优先为Leader

5.统计投票

每次投票后,服务器统计所有投票,判断是否有过半的机器收到相同的投票,如果某个投票达到一半的要求,则认为该投票提出者可以成为Leader。

6.改变服务器状态

一旦确定了Leader,每个服务器都更新自己的状态,Leader变更为Leading,Follower变更为Following
正常情况下一旦选出一个Leader则一直会保持,除非Leader服务器宕掉,则再进行重新选举。

服务器运行时期的Leader选举

1.变更状态

当Leader宕机后,余下的所非Observer的服务器都会将自己的状态变更为Looking,然后开启新的Leader选举流程。

2.每个服务器发出一个投票。

生成(SID,ZXID)信息,注意运行期间的ZXID可能是不同的,但是在投票时都会将自己投为Leader,然后发送给其他的服务器。

3.接收来自各个服务器的投票

与启动时过程相同

4.处理投票

与启动时过程相同

5.统计投票

与启动时过程相同

6.改变服务器状态

与启动时过程相同

资料

LeetCode 二叉树的层次遍历

第102题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal

如何遍历一棵树

有两种通用的遍历树的策略:

  • 深度优先搜索(DFS)

在这个策略中,我们采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支。

深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为先序遍历,中序遍历和后序遍历。

  • 宽度优先搜索(BFS)

我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。

解题思路

方法 1:迭代+队列

我们将树上顶点按照层次依次放入队列结构中,队列中元素满足 FIFO(先进先出)的原则。使用 Queue 接口中的 LinkedList实现。

算法实现如下:

  • 初始化队列只包含一个节点 root。
  • 初始一个List变量result,用来做返回结果
    当队列非空的时候,循环开始:
  • 计算当前层有多少个元素:等于队列的长度
  • 初始一个List变量subResult,用来存当前层的节点值
  • 将这些元素从队列中弹出,将他们的值加入subResult列表中
  • 将他们的孩子节点作为下一层压入队列中
  • 进入下一层,将当前层subResult add到result中
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 Solution102_1 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();
return BFS(root);
}

List<List<Integer>> BFS(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<List<Integer>> result = new LinkedList<>();
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
subResult.add(node.val);
}
result.add(subResult);
}
return result;
}
}

方法 2:递归

首先确认树非空,然后调用递归函数 DFS(node,result,level),参数是当前节点、返回结果列表、节点的层次。

算法实现如下:

  • result列表的长度小于level,为result add一个新列表
  • 为当前层的result列表add节点值,即result.get(level - 1).add(node.val)
  • 如果有左孩子,调用DFS(node.left, result, level + 1),进入递归
  • 如果有右孩子,调用DFS(node.right, result, level + 1),进入递归
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 Solution102_2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<List<Integer>> result = new LinkedList<>();

DFS(root, result, 1);
return result;
}

void DFS(TreeNode node, List<List<Integer>> result, int level) {
if (result.size() < level) {
result.add(new LinkedList<>());
}
result.get(level - 1).add(node.val);
if (node.left != null) {
DFS(node.left, result, level + 1);
}
if (node.right != null) {
DFS(node.right, result, level + 1);
}
}
}

完整代码

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
public class Sub102 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

Solution102_2 solution = new Solution102_2();
List<List<Integer>> list = solution.levelOrder(root);
for (List<Integer> subList : list) {
System.out.println(subList.toString());
}
}
}

/**
* 广搜+队列
*/
class Solution102_1 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();
return BFS(root);
}

List<List<Integer>> BFS(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<List<Integer>> result = new LinkedList<>();
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
subResult.add(node.val);
}
result.add(subResult);
}
return result;
}
}

/**
* 深搜+递归
*/
class Solution102_2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<List<Integer>> result = new LinkedList<>();

DFS(root, result, 1);
return result;
}

void DFS(TreeNode node, List<List<Integer>> result, int level) {
if (result.size() < level) {
result.add(new LinkedList<>());
}
result.get(level - 1).add(node.val);
if (node.left != null) {
DFS(node.left, result, level + 1);
}
if (node.right != null) {
DFS(node.right, result, level + 1);
}
}
}

资料

LeetCode 二叉树的锯齿形层次遍历

第103题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:

[
[3],
[20,9],
[15,7]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

解题思路

基于二叉树层序遍历改一点代码即可

  • 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的抽象数据类型。双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。
  • 本题和普通的层序遍历区别在于如何正确的选取加入子节点的顺序以及先后.
  • 利用双端队列,左进的时候,右出;右进的时候,左出。正好满足一层正序遍历,一层逆序遍历。

代码实现

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
class Solution103_1 {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
return BFS(root);
}

List<List<Integer>> BFS(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.addLast(root);
List<List<Integer>> result = new LinkedList<>();
boolean reverse = true;
while (!deque.isEmpty()) {
int size = deque.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node;
if (reverse) {
//头出
node = deque.pollFirst();

//尾进
if (node.left != null) {
deque.addLast(node.left);
}
if (node.right != null) {
deque.addLast(node.right);
}
} else {
//尾出
node = deque.pollLast();

//头进
if (node.right != null) {
deque.addFirst(node.right);
}
if (node.left != null) {
deque.addFirst(node.left);
}
}
subResult.add(node.val);
}
result.add(subResult);
reverse = !reverse;
}
return result;
}
}

完整代码

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
public class Sub103 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

// TreeNode root = new TreeNode(1);
// root.left = new TreeNode(2);
// root.right = new TreeNode(3);
// root.left.left = new TreeNode(4);
// root.right.right = new TreeNode(5);

Solution103_1 solution = new Solution103_1();
List<List<Integer>> list = solution.zigzagLevelOrder(root);
for (List<Integer> subList : list) {
System.out.println(subList.toString());
}
}
}

class Solution103_1 {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
return BFS(root);
}

List<List<Integer>> BFS(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.addLast(root);
List<List<Integer>> result = new LinkedList<>();
boolean reverse = true;
while (!deque.isEmpty()) {
int size = deque.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node;
if (reverse) {
//头出
node = deque.pollFirst();

//尾进
if (node.left != null) {
deque.addLast(node.left);
}
if (node.right != null) {
deque.addLast(node.right);
}
} else {
//尾出
node = deque.pollLast();

//头进
if (node.right != null) {
deque.addFirst(node.right);
}
if (node.left != null) {
deque.addFirst(node.left);
}
}
subResult.add(node.val);
}
result.add(subResult);
reverse = !reverse;
}
return result;
}
}

资料

LeetCode 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树

第108题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

解题思路

  • 从定义我们知道,BST的中序遍历为一个递增序列,给定的数组其实就是中序遍历结果
  • 取有序数组的中间值做根,左边部分做左树,右边部分做右树如此循环迭代去二分就可还原这棵BST树

代码实现

1.二分+递归实现

每次取数组的中间值,作为二分搜索树的中间节点,依次递归下去即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//二分+递归实现
class Solution108_1 {
public TreeNode sortedArrayToBST(int[] nums) {
return convertToBST(nums, 0, nums.length - 1);
}

TreeNode convertToBST(int[] nums, int begin, int end) {
if (begin > end) return null;
//取中值
int mid = begin + (end - begin) / 2;
TreeNode root = new TreeNode(nums[mid]);
//左叶子树
root.left = convertToBST(nums, begin, mid - 1);
//右叶子树
root.right = convertToBST(nums, mid + 1, end);
return root;
}
}

2.利用堆栈,去递归化实现

  • 定义一个栈,用来存将要处理数组的左索引和右索引值
  • 定义另一个栈,用来存树的节点,因为节点是先初始化,后更新节点值的迭代过程。所以需要借用堆栈先建好节点,建立好关系。
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
//非递归实现
class Solution108_2 {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
Stack<Integer> stack = new Stack<Integer>();
//数组最大索引值入栈
stack.add(nums.length - 1);
//数组最小索引值入栈
stack.add(0);

Stack<TreeNode> tree = new Stack<TreeNode>();
TreeNode root = new TreeNode(0);
//随便new树节点入栈
tree.add(root);

while (!stack.isEmpty()) {
int left = stack.pop();
int right = stack.pop();
//求出中间节点索引值
int mid = left + (right - left) / 2;
TreeNode node = tree.pop();
//更新根节点值
node.val = nums[mid];

//计算左叶子节点最大最小索引值
int r = mid - 1, l = left;
//如果存在左叶子节点
if (l <= r) {
node.left = new TreeNode(0);
//随便new个树节点入栈
tree.add(node.left);

//对应右索引值入栈
stack.push(r);
//对应左索引值入栈
stack.push(l);
}

//计算右节点最大最小索引值
l = mid + 1;
r = right;
if (l <= r) {
node.right = new TreeNode(0);
//随便new个树节点入栈
tree.add(node.right);

//对应右索引值入栈
stack.push(r);
//对应左索引值入栈
stack.add(l);
}
}
return root;
}
}

总结

不出所料,通过提交代码发现堆栈实现会比递归执行效率慢很多,这是因为:

  • 堆栈实现需要频繁的push(入栈)、pop(出栈)操作导致性能下降

资料

LeetCode 把二叉搜索树转换为累加树

第538题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree

概念

二叉搜索树

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

解题思路

  • 从定义我们知道,BST的中序遍历为一个递增序列
  • 我们将中序遍历倒置(先右子树,后根节点、再左子树),即可实现一个递减序列
  • 遍历该序列,从大往小累加并更新节点值,即可实现累加树(节点值=原来的节点值加上所有大于它的节点值之和)

代码实现

1.递归倒置中序遍历思路实现

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 Solution1 {
public TreeNode convertBST(TreeNode root) {
addSum(root, 0);
return root;
}

public int addSum(TreeNode node, int parentVal) {
//如果没有节点了,返回父节点值
if (node == null) {
return parentVal;
}

//累加右边所有节点值
int rVal = addSum(node.right, parentVal);

//当前节点值=右边所有节点累加值+当前节点值
node.val += rVal;
//System.out.println("当前节点值:" + node.val);

//累加左边所有节点值
int lVal = addSum(node.left, node.val);
return lVal;
}
}

2.利用堆栈,去递归化实现

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 Solution2 {
public TreeNode convertBST(TreeNode root) {
TreeNode oRoot = root;
Stack<TreeNode> stack = new Stack();
int sum = 0;
while (true) {
//右节点入栈
while (root != null) {
stack.push(root);
root = root.right;
}

//如果栈为空退出循环
if (stack.empty()) {
break;
}
//否则出栈进入计算
else {
TreeNode node = stack.pop();
//更新节点值
node.val += sum;
//更新sum值
sum = node.val;
//左节点进入[右节点入栈]
root = node.left;
}
}
//返回原树,此时该树所有节点已做更新
return oRoot;
}
}

总结

我们通过提交代码发现堆栈实现会比递归执行效率慢很多,这是因为:

  • 尾递归被jvm编译器识别并针对其迭代对应进行优化处理过
  • 堆栈实现需要频繁的push(入栈)、pop(出栈)操作导致性能下降

资料