默克尔树又称哈希树，一种树形结构，被广泛应用于密码学相关领域。

特点：

• 叶子节点除了包含数据之外，还包含自身的哈希

• 根节点和中间节点的哈希是通过他们的孩子计算而来

数据结构：

struct Node {
  uint val;
  string hash;
  Node[] children;
}

可以利用这个特点，来快速验证一组数据的正确性。

下面列几个常见的应用。

1. 快速验证数据是否正确

把数据都存储在最下层的叶子节点，即 L1 ~ L4， 因为根节点和中间节点的哈希都是根据叶子节点计算而来，所以只比较根节点，就能快速判断数据的正确性。

2. 快速定位有问题的数据

在根节点不一致时，我们逐级往下查找子节点不一致的地方，能以 O(lgN) 的时间找到出问题的节点。