一、题目

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

Leetcode：https://leetcode.cn/problems/count-complete-tree-nodes/

遍历二叉树的过程是 O(n) 的时间复杂度，我们需要一个时间复杂度更低的算法

二、分析

完全二叉树我们来看如下两种情况：

最后一层的最后一个节点在右子树，所以 head->left 是一棵满二叉树

一、题目

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。

Leetcode 99 题：https://leetcode.cn/problems/recover-binary-search-tree/

二、分析

一个二叉树搜索树，他的中序遍历一定是升序的。如果像题目中的一样，有两个节点的值被错误的交换，那么对应的中序遍历的结果中就会有一个或者两个地方出现 arr[i] > arr[i+1]。因此我们有三步操作。

• 通过中序遍历，拿到数组

Morris 遍历细节

假设来到当前节点 cur，开始时 cur 来到头节点位置

1. 如果 cur 没有左孩子，cur 向右移动 （cur = cur.right）
2. 如果 cur 有左孩子，找到左子树上最右的节点 mostRight

一、题目

如下，有一个二叉树，请按照 Z 字形打印

打印结果为：

1
2
3
4

Level 1 from left to right: 1
Level 2 from right to left: 3 2
Level 3 from left to right: 4 5 6
Level 4 from right to Left: 8 7

一、题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

Leetcode：https://leetcode.cn/problems/binary-tree-right-side-view/

二、分析

本题目比较简单，层序遍历的思路。只需要保存每次层序遍历过程中最右边的节点即可

分布式ID

分布式 ID 也称全局唯一 ID 。

一、分布式 ID 需要满足什么条件

• 全局唯一：必须保证ID是全局性唯一的，基本要求
• 高性能：高可用低延时，ID生成响应要块，否则反倒会成为业务瓶颈
• 高可用：100%的可用性是骗人的，但是也要无限接近于100%的可用性

缓存

错误的做法

做法：更新数据时，先删除缓存，然后再更新数据库。查询操作时，发现缓存中没有数据然后会从数据库中更新到缓存中。错误的逻辑。

场景：两个并发操作，一个是更新操作，另一个是查询操作。更新操作删除缓存后，查询操作没有命中缓存，则把老数据读出来后放到了缓存。更新操作更新了数据库。于是，在缓存中的数据还是老的数据，导致缓存中的数据是脏的，而且一直是脏的

更新缓存的 Design Pattern 有四种：Cache aside，Read through，Write through，Write behind caching。

一、Cache Aside Pattern

1. 介绍

• 更新操作：先把数据存到数据库中，成功后，再让缓存失效

一、快照

在可重复读隔离级别下，事务在启动时，就拍了“快照”，这个快照是基于整库的。InnoDB 中每个事务有一个唯一的事务 ID，叫做 transaction id，他是在事务开始时向 InnoDB 的事务系统申请的，是按申请顺序严格递增的。

而每行数据都是有多个版本的。每次事务更新数据时，都会生成一个新的数据版本，并且把 transaction id 赋值给这个数据版本的事务 ID，记住 row trx_id。同时，旧的数据版本要保留，并且在新的数据版本中，能够有信息可以直接获取他。

也即是说，数据表中的一行记录，其实可能有多个版本，每个版本有自己的 row trx_id。

1. 举例子

如下是一个记录被多个事务连续更新后的状态：

一、悲观锁

对数据抱悲观态度，认为数据并发修改的概率比较大，因此在数据修改之前先加锁。采用 “先取锁再访问” 的策略，为数据处理的安全提高了保证。

但是在效率方面，处理加锁的机制会让数据库产生额外的开销，还有增加死锁的机会。另外，还会降低并行度，一个事务如果锁定了某行数据，其他事务就必须等待该事务处理完才可以处理那行数据。

1. 实现方式

悲观锁的实现，往往依靠数据库提供的锁机制。在数据库中，悲观锁的流程如下：

• 在对记录进行修改前，先尝试为该记录加上排他锁（exclusive locking）

事务会把数据库从一种一致状态转换为另一种一致状态。事务保证数据库在提交工作时，要么全部成功，要么全部失败。在 MySQL中，事务支持是在引擎层实现的。

一、 事务的 ACID 特性

ACID（Atomicity、Consistency、Isolation、Durability，即原子性、一致性、隔离性、持久性）

原子性：数据库事务是不可分割的工作单元。事务中的数据库操作都执行成功，才算整个事务成功；事务中任何一个SQL语句执行失败，已经执行成功的SQL语句也必须撤销，数据库保持应该退回到执行事务前的状态

一致性：事务将数据库从一种状态转变为下一种一致的状态。在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏。而且一致性依赖于应用层开发者，数据库会保证所有的约束没有被打破，业务应该保证对数据有一定的约束。