克尔树是区块链技术的一个基本概念。它们是一种特殊的二进制树,用于编码大块的信息。默克尔树的酷之处在于,它们是一种自下而上的 "建立",并允许你验证某些值是否存在于树中,而不需要在树的每个元素上循环。正如我们会看到的,这可能非常有用。
默克尔树是一种哈希树,其中每个叶子节点都标有数据块的加密哈希值,而每个非叶子节点都标有其子节点的加密哈希值的标签。大多数哈希树的实现是二进制的(每个节点有两个子节点),但它们也可以有更多的子节点。
一个典型的默克尔树看起来是这样的。
(引用自 using-merkle-trees-for-nft-whitelists[1])
让我解释一下发生了什么。树的所有叶节点,即没有任何其他子节点的节点,都包含您要编码的数据的哈希值。请注意,您要在树中编码的值始终只是叶节点的一部分。由于它是二叉树,每个非叶节点都有两个孩子。当您从叶节点向上移动时,父节点将拥有叶节点组合哈希的哈希,依此类推。
当您继续这样做时,最终您将到达单个顶级节点,称为 Merkle 树根,这将发挥非常重要的作用。
假设我们有 4 个事务:“事务 A”、B、C 和 D。它们都在同一个块中执行。这些交易中的每一个都将被散列。让我们分别称这些哈希为“哈希 A”、B、C 和 D。
以下是这些交易的 Merkle Tree:
当这些交易汇总到一个块中时,块头将包含 Merkle Root,Hash ABCD。到目前为止,所有矿工都拥有所有交易的副本,因此拥有所有交易哈希。任何矿工都可以按需重建 Merkle 树,这意味着每个矿工都可以针对同一组交易独立到达同一个 Merkle 根。
这允许任何矿工验证欺诈交易。假设有人试图引入虚假交易而不是交易 D。让我们将此称为交易 E。因为此交易与交易 D 不同,所以哈希也会不同。Transaction E的Hash就是Hash E。C和E的Hash加在一起就是Hash CE,与Hash CD不同。当哈希 AB 和 CE 一起哈希时,你得到哈希 ABCE。由于哈希 ABCE 与哈希 ABCD 不同,我们可以得出交易 E 是欺诈性的结论。
矿工可以在自己的区块中重新计算 Merkle Root 并尝试将该版本发布到区块链,但由于每个其他矿工都有不同的 Merkle Root,因此欺诈矿工很容易被拒绝。
在谈论 IPFS 时,我们之前已经介绍过哈希函数,但只是回顾一下:将事务 A 哈希到哈希 A 中,使用了单向加密哈希函数。一旦散列,Hash A 就不能变成 Transaction A;哈希是不可逆的。
每个区块链使用不同的哈希函数,但它们都具有相同的共同属性。
当传递给散列函数时,相同的输入总是具有相同的输出。
计算输入值的哈希值很快。
给定一个结果哈希,几乎不可能确定输入。即散列函数是单向函数。例如:给定y,很难找到x这样的h(x)=y
两个不同的输入永远不会产生相同的输出。
Merkle Trees 允许快速验证数据完整性。
与整个事务集相比,已用完的磁盘空间非常少。出于这个原因,Merkle Root 包含在块头中。
如果你有两组不同的交易,用默克尔树验证它们是否相同比验证每一个单独的交易要快。只需知道 Merkle Root,就可以验证一个块没有被修改。
Merkle 树不仅用于区块链应用程序。一些使用 Merkle 树的流行应用程序是:
那么,我们如何真正验证某些数据是默克尔树的一部分呢?
您不希望验证器遍历 Merkle 树的每个叶节点,因为它可能非常大,那么我们如何以更有效的方式做到这一点?
假设Verifier唯一有Merkle Root r,即树的顶级父节点。你,作为一个Prover,想要证明默克尔树中存在Verifier一些价值。K
为此,您可以生成一个Merkle Proof. Merkle Proof让我们尝试通过示例 Merkle 树来了解 a 的实际含义。
(参考默克尔证明解释[6])
主要思想如下:如果您可以给出 的Verifier值K,以及树中的所有相关节点,这些节点被散列在一起以构建r散列,则Verifier可以将计算的根值与r它们已经拥有的值进行比较。如果它们是相同的散列,那一定意味着它K实际上存在于 Merkle 树中,因为您不可能使用不同的输入数据生成相同的 Merkle Root 散列。
在上图中,让我们考虑必须向验证者提供哪些信息,才能积极地向K作为默克尔树一部分的验证者证明。
再次重要的是要记住,只有一个给定的节点组合可以生成这个唯一的根r,因为 Merkle 树是一个 collision-resistant hash function,这意味着它是一个哈希函数,给定两个输入几乎不可能产生相同的输出。
对于我们给定的示例,我们只需要提供以下节点即可证明 H[K] 确实存在于我们的节点中:
此时,如果 的计算值与 VerifierH(ABCDEFGHIJKLMNOP)先前已知的值匹配r,则在 Merkle Tree 中存在一定为真,K否则哈希值将不一样。
这比遍历整个 Merkle 树要高效得多,因为对于具有n多个元素的树,您只需提供粗略log(n)的元素作为证明的一部分(树的每个“级别”一个)。这意味着如果您有大量数据,Merkle 树比存储数组或映射更有效。
当 ENS 启动他们的代币合约时,他们将 $ENS 代币空投到超过 100,000 个钱包地址。他们能够在汽油费极高的情况下以比将钱包地址存储在数组中的价格低得多的价格部署他们的合约(即使存储几百个地址也很容易超过汽油费)块的限制) - https://etherscan.io/tx/0xdfc76788b13ab1c033c7cd55fdb7a431b2bc8abe6b19ac9f7d22f4105bb43bff
由于验证者不需要存储整个 Merkle Tree 来验证是否是其中的一部分,Merkle Trees 实际上对于某些事情非常方便。
在大二,我们创建了一个将用户地址存储在映射中的白名单 dApp。虽然这种方法有效,但在智能合约存储中存储数据是迄今为止你可以做的最昂贵的事情,就 gas 而言。那么如果你必须存储 1000 个地址呢?如果是一万呢?10万呢?
到那时,直接使用智能合约存储是不可行的,仅仅将人们列入白名单就很容易花费数百万美元。另一方面,你可以建立一个默克尔树,然后将默克尔根值存储在合约中——一个微不足道的bytes32值。在这种情况下,合约现在是Verifier,并且希望使用他们的白名单来铸造 NFT 的用户,比方说,成为Provers他们确实是白名单的一部分的证明。让我们看看这是如何工作的。
让我们看看这一切在我们的白名单示例中是如何实际工作的。
npm init --yes
npm install --save-dev hardhat
npm install --save-dev @nomiclabs/hardhat-waffle ethereum-waffle chai @nomiclabs/hardhat-ethers ethers
npx hardhat
现在您的Hardhat文件夹已设置完毕。
我们还需要安装一些额外的依赖项来执行一切。因此,再次在指向根目录的终端中执行以下命令:
npm install @openzeppelin/contracts keccak256 merkletreejs
contracts现在首先在您的文件夹中创建一个名为的文件Whitelist.sol并将以下代码行添加到其中
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
contract Whitelist {
bytes32 public merkleRoot;
constructor(bytes32 _merkleRoot) {
merkleRoot=_merkleRoot;
}
function checkInWhitelist(bytes32[] calldata proof, uint64 maxAllowanceToMint) view public returns (bool) {
bytes32 leaf=keccak256(abi.encode(msg.sender, maxAllowanceToMint));
bool verified=MerkleProof.verify(proof, merkleRoot, leaf);
return verified;
}
}
这里到底发生了什么?因此,正如我们提到的,我们不会在合约中存储每个用户的地址,而是只存储在构造函数中初始化的默克尔树的根。
我们还有另一个函数checkInWhitelist,它接受 aproof和maxAllowanceToMint。 maxAllowanceToMint是一个变量,用于跟踪给定地址可以铸造的 NFT 数量。
对于这个用例,我们实际存储在 Merkle 树中的值是存储用户的地址以及他们被允许铸造的 NFT 数量。您可以在 Merkle Trees 中存储您想要的任何数据,但这适用于我们的示例。该地址所在的叶节点的哈希值可以通过首先将发送者的地址和maxAllowanceToMint字节字符串编码来计算,该字符串进一步传递给keccak256哈希函数,哈希函数需要哈希字符串来生成哈希值。
现在我们使用 OpenZeppelin 的MerkleProof库来验证用户发送的证明确实有效。请注意,Openzeppelin 如何执行高级别的验证类似于我们在教程前面讨论的 Merkle 证明的验证。
接下来,让我们编写一个测试来帮助确定我们合约中的代码是否真的有效。
在您的test文件夹中创建一个新文件merkle-root.js并将以下代码行添加到其中
const { expect }=require("chai");
const { ethers }=require("hardhat");
const keccak256=require("keccak256");
const { MerkleTree }=require("merkletreejs");
function encodeLeaf(address, spots) {
// Same as `abi.encodePacked` in Solidity
return ethers.utils.defaultAbiCoder.encode(
["address", "uint64"],
[address, spots]
);
}
describe("Check if merkle root is working", function () {
it("Should be able to verify if a given address is in whitelist or not", async function () {
// Get a bunch of test addresses
const [owner, addr1, addr2, addr3, addr4, addr5]=await ethers.getSigners();
// Create an array of elements you wish to encode in the Merkle Tree
const list=[
encodeLeaf(owner.address, 2),
encodeLeaf(addr1.address, 2),
encodeLeaf(addr2.address, 2),
encodeLeaf(addr3.address, 2),
encodeLeaf(addr4.address, 2),
encodeLeaf(addr5.address, 2),
];
// Create the Merkle Tree using the hashing algorithm `keccak256`
// Make sure to sort the tree so that it can be produced deterministically regardless
// of the order of the input list
const merkleTree=new MerkleTree(list, keccak256, {
hashLeaves: true,
sortPairs: true,
});
// Compute the Merkle Root
const root=merkleTree.getHexRoot();
// Deploy the Whitelist contract
const whitelist=await ethers.getContractFactory("Whitelist");
const Whitelist=await whitelist.deploy(root);
await Whitelist.deployed();
// Compute the Merkle Proof of the owner address (0'th item in list)
// off-chain. The leaf node is the hash of that value.
const leaf=keccak256(list[0]);
const proof=merkleTree.getHexProof(leaf);
// Provide the Merkle Proof to the contract, and ensure that it can verify
// that this leaf node was indeed part of the Merkle Tree
let verified=await Whitelist.checkInWhitelist(proof, 2);
expect(verified).to.equal(true);
// Provide an invalid Merkle Proof to the contract, and ensure that
// it can verify that this leaf node was NOT part of the Merkle Tree
verified=await Whitelist.checkInWhitelist([], 2);
expect(verified).to.equal(false);
});
});
在这里,我们首先让一些签名者使用 hardhat 的扩展 ethers 包进行测试。
然后我们创建一个节点列表,这些节点都使用ethers.utils.defaultAbiCoder.encode
使用我们输入列表中的MerkleTree类,指定我们的散列函数,并将节点的排序设置为merkletreejs``keccak256``true
创建 后Merkle Tree,我们通过调用getHexRoot函数来获取它的根。我们使用这个根来部署我们的Whitelist合约。
在我们的合约被验证后,我们可以checkInWhitelist通过提供证明来调用我们的合约。所以现在在这里我们将检查(owner.address, 2)我们的数据集中是否存在。为了生成证明,我们对 的编码值进行哈希处理,并使用库中的函数(owner.address, 2)生成证明 。getHexProof``merkletreejs
然后将该证明checkInWhitelist作为参数发送,该参数进一步返回 true 值以表示(owner.address, 2)存在。
要运行测试,请从目录的根目录执行以下命令:
npx hardhat test
如果你所有的测试都通过了,你就成功地了解了 Merkle 树是什么以及它如何用于白名单
希望你玩得开心!!
干杯
[1] using-merkle-trees-for-nft-whitelists: https://medium.com/@ItsCuzzo/using-merkle-trees-for-nft-whitelists-523b58ada3f9
[2] IPFS: https://en.wikipedia.org/wiki/InterPlanetary_File_System
[3] Github: https://github.com/
[4] AWS DynamoDB: https://aws.amazon.com/dynamodb
[5] Apache Cassandra: https://cassandra.apache.org/_/index.html
[6] 默克尔证明解释: https://medium.com/crypto-0-nite/merkle-proofs-explained-6dd429623dc5
[7] 教程: https://medium.com/spidernitt/testing-with-mocha-and-chai-b8da8d2e10f2
增的结构标签
section元素
表示页面中的一个内容区块,比如章节、页眉、页脚或页面的其他部分。可以和h1、 h2...等元素结合起来使用,表示文档结构。
例:HTML5中<section>...</section>;HTML4中<div>...</div>。
article元素
表示页面中一块与上下文不相关的独立内容。比如一篇文章。
aside元素
表示article元素内容之外的、与article元素内容相关的辅助信息。
header元素
表示页面中一个内容区块或真个页面的标题。
hgroup元素
表示对真个页面或页面中的一个内容区块的标题进行组合。
footer元素
表示整个页面或页面中一个内容区块的脚注。一般来说,他会包含创作者的姓名、创作日期以及创作者的联系信息。
nav元素
表示页面中导航链接的部分。
figure元素
表示一段独立的流内容,一般表示文档主体流内容中的一个独立单元。使用figcaption元素为figure元素组添加标题。
figure 定义媒介内容的分组, 以及它们的标题。
figcaption 定义 figure 元素的标题。
例如:
<figure>
<figcaption>PRC</figcaption>
<p>The People's Republic of China was born in 1949</p>
</figure>
HTML4中常写作
<dl>
<h1>prc</h1>
<p>The People's Republic of China was born in 1949</p>
</dl>
新增的其他元素
video元素
定义视频。像电影片段或其他视频流。例:
<video src="movie.ogg" controls="controls">video元素</video>
HTML4中写法:
<object type="video/ogg" data="move.ogv">
<param name="src" value="movie.ogv">
</object>
audio元素
定义音频。如音乐或其他音频流。例:
<audio src="someaudio.wav">audio元素</audio>
html4中写法:
<object tyle="application/ogg" data="someaudio.wav">
<param name="src" value="someaudio.wav">
</object>
embed元素
用来嵌入内容(包括各种媒体)。格式可以是Midi、Wav、AIFF、AU、MP3,flash等。例:<embed src="flash.swf" />
HTML4中代码示例<object data="flash.swf" type="application/x-shockwave-flash"><object>
mark元素
主要用来在视觉上向用户呈现哪些需要突出显示或高亮显示的文字。典型应用搜索结果中高亮显示搜素关键字。
HTML5<mark></mark>;HTML4 <span></span>。
progress元素
表示运行中的进程,可以使用progress元素显示JavaScript中耗时时间函数的进程。等待中……、请稍后等。<progress></progress>。
time元素
表示日期或时间,也可以两者同时。
ruby元素
定义 ruby 注释(中文注音或字符)。
与 <ruby> 以及 <rt> 标签一同使用。ruby 元素由一个或多个字符(需要一个解释/发音)和一个提供该信息的 rt 元素组成,
还包括可选的 rp 元素,定义当浏览器不支持 "ruby" 元素时显示的内容。
<ruby>
汉朝<rt><rp>(</rp>西汉和东汉<rp>)</rp></rt>
</ruby>
rt元素
定义字符(中文注音或字符)的解释或发音。
rp元素
在 ruby 注释中使用, 以定义不支持 ruby 元素的浏览器所显示的内容。
wbr元素
表示软换行。与br元素的区别:br元素表示此处必须换行;wbr表示浏览器窗口或父级元素足弓宽时(没必要换行时),
不换行,而宽度不够时主动在此处换行。
canvas元素
定义图形,比如图表和其他图像。<canvas> 元素只是图形容器(画布),必须使用脚本来绘制图形。
<canvas id="myCanvas"></canvas>
<script type="text/javascript">
var canvas=document.getElementById('myCanvas');
var ctx=canvas.getContext('2d');
ctx.fillStyle='#FF0000';
ctx.fillRect(0,0,80,100);
</script>
command元素 各版本浏览器支持有问题
表示命令按钮,比如单选按钮、复选框或按钮。
只有当 command 元素位于 menu 元素内时,该元素才是可见的。否则不会显示这个元素,但是可以用它规定键盘快捷键。。
<menu>
<command onclick="alert('Hello World')">
Click Me!</command>
</menu>
details标签
用于描述文档或文档某个部分的细节 。
可与 summary 标签配合使用,summary可以为 details 定义标题。
标题是可见的,用户点击标题时,会显示出 details。summary应该是details的第一个子元素。
<details>
<summary>迪丽热巴</summary>
<p>迪丽热巴(Dilraba),1992年6月3日出生于新疆乌鲁木齐市,中国内地影视女演员。</p>
</details>
fieldset标签
组合表单中的相关元素
fieldset 标签用于从逻辑上将表单中的元素组合起来。
legend 标签为 fieldset 元素定义标题。
<form>
<fieldset>
<legend>健康信息</legend>
身高:<input type="text" />
体重:<input type="text" />
</fieldset>
</form>
datalist标签
定义选项列表。请与 input 元素配合使用该元素,来定义 input 可能的值。
datalist 及其选项不会被显示出来,它仅仅是合法的输入值列表。使用 input 元素的 list 属性来绑定 datalist。
<input id="myCar" list="cars" />
<datalist id="cars">
<option value="BMW">
<option value="Ford">
<option value="Volvo">
</datalist>
datagrid标签 如何用?
定义可选数据的列表。datagrid 作为树列表来显示。
如果把 multiple 属性设置为 true,则可以在列表中选取一个以上的项目。
keygen标签 如何用?
标签规定用于表单的密钥对生成器字段。
当提交表单时,私钥存储在本地,公钥发送到服务器。
<form action="demo_keygen.asp" method="get">
Username: <input type="text" name="usr_name" />
Encryption: <keygen name="security" />
<input type="submit" />
</form>
output标签
定义不同类型的输出,比如脚本的输出。
<form action="form_action.asp" method="get" name="sumform">
<output name="sum"></output>
</form>
source标签
标签为媒介元素(比如 <video> 和 <audio>)定义媒介资源。
menu标签
定义菜单列表。当希望列出表单控件时使用该标签。注意与nav的区别,menu专门用于表单控件。
<menu>
<li><input type="checkbox" />Red</li>
<li><input type="checkbox" />blue</li>
</menu>
abbr: 标记一个缩写
The <abbr title="People's Republic of China">PRC</abbr> was founded in 1949.
显示结果
The PRC was founded in 1949.
mark标签
定义有记号的文本。
<mark>有记号的文本</mark>
progress 定义任何类型的任务的进度。
<progress min="0" max="100" value="60"></progress>
上下本文的提纲,这个是我用 mindmap 画的一个脑图,之后我会继续完善,将其他专题逐步完善起来。
?
大家也可以使用 vscode blink-mind 打开源文件查看,里面有一些笔记可以点开查看。源文件可以去我的公众号《力扣加加》回复脑图获取,以后脑图也会持续更新更多内容。vscode 插件地址:https://marketplace.visualstudio.com/items?itemName=awehook.vscode-blink-mind
?
本系列包含以下专题:
首先亮一下本文的主角 - 树(我的化妆技术还行吧^_^):
树标签[1]在 leetcode 一共有 「175 道题」。 为了准备这个专题,我花了几天时间将 leetcode 几乎所有的树题目都刷了一遍。
除了 35 个上锁的,1 个不能做的题(1628 题不知道为啥做不了), 4 个标着树的标签但却是图的题目,其他我都刷了一遍。通过集中刷这些题,我发现了一些有趣的信息,今天就分享给大家。
大家好,我是 lucifer。今天给大家带来的是《树》专题。另外为了保持章节的聚焦性和实用性,省去了一些内容,比如哈夫曼树,前缀树,平衡二叉树(红黑树等),二叉堆。这些内容相对来说实用性没有那么强,如果大家对这些内容也感兴趣,可以关注下我的仓库 leetcode 算法题解[2],大家有想看的内容也可以留言告诉我哦~
另外要提前告知大家的是本文所讲的很多内容都很依赖于递归。关于递归的练习我推荐大家把递归过程画到纸上,手动代入几次。等大脑熟悉了递归之后就不用这么辛苦了。 实在懒得画图的同学也可以找一个可视化递归的网站,比如 https://recursion.now.sh/。 等你对递归有了一定的理解之后就仔细研究一下树的各种遍历方法,再把本文看完,最后把文章末尾的题目做一做,搞定个递归问题不大。
?
文章的后面《两个基本点 - 深度优先遍历》部分,对于如何练习树的遍历的递归思维我也提出了一种方法
?
最后要强调的是,本文只是帮助你搞定树题目的常见套路,但不是说树的所有题目涉及的考点都讲。比如树状 DP 这种不在本文的讨论范围,因为这种题更侧重的是 DP,如果你不懂 DP 多半是做不出来的,你需要的是学完树和 DP 之后再去学树状 DP。如果你对这些内容感兴趣,可以期待我的后续专题。
提到树大家更熟悉的是现实中的树,而现实中的树是这样的:
而计算机中的树其实是现实中的树的倒影。
计算机的数据结构是对现实世界物体间关系的一种抽象。比如家族的族谱,公司架构中的人员组织关系,电脑中的文件夹结构,html 渲染的 dom 结构等等,这些有层次关系的结构在计算机领域都叫做树。
首先明确一下,树其实是一种逻辑结构。比如笔者平时写复杂递归的时候,尽管笔者做的题目不是树,也会画一个递归树帮助自己理解。
?
树是一种重要的思维工具
?
以最简单的计算 fibonacci 数列为例:
function fn(n) {
if (n == 0 || n == 1) return n;
return fn(n - 1) + fn(n - 2);
}
很明显它的入参和返回值都不是树,但是却不影响我们用树的思维去思考。
继续回到上面的代码,根据上面的代码可以画出如下的递归树。
其中树的边表示的是返回值,树节点表示的是需要计算的值,即 fn(n)。
以计算 5 的 fibbonacci 为例,过程大概是这样的(动图演示):
「这其实就是一个树的后序遍历」,你说树(逻辑上的树)是不是很重要?关于后序遍历咱们后面再讲,现在大家知道是这么回事就行。
大家也可以去 这个网站[3] 查看上面算法的单步执行效果。当然这个网站还有更多的算法的动画演示。
?
上面的图箭头方向是为了方便大家理解。其实箭头方向变成向下的才是真的树结构。
?
广义的树真的很有用,但是它范围太大了。 本文所讲的树的题目是比较狭隘的树,指的是输入(参数)或者输出(返回值)是树结构的题目。
?
树的基本概念难度都不大,为了节省篇幅,我这里简单过一下。对于你不熟悉的点,大家自行去查找一下相关资料。我相信大家也不是来看这些的,大家应该想看一些不一样的东西,比如说一些做题的套路。
?
树是一种非线性数据结构。树结构的基本单位是节点。节点之间的链接,称为分支(branch)。节点与分支形成树状,结构的开端,称为根(root),或根结点。根节点之外的节点,称为子节点(child)。没有链接到其他子节点的节点,称为叶节点(leaf)。如下图是一个典型的树结构:
每个节点可以用以下数据结构来表示:
Node {
value: any; // 当前节点的值
children: Array<Node>; // 指向其儿子
}
其他重要概念:
二叉树是树结构的一种,两个叉就是说每个节点「最多」只有两个子节点,我们习惯称之为左节点和右节点。
?
注意这个只是名字而已,并不是实际位置上的左右
?
二叉树也是我们做算法题最常见的一种树,因此我们花大篇幅介绍它,大家也要花大量时间重点掌握。
二叉树可以用以下数据结构表示:
Node {
value: any; // 当前节点的值
left: Node | null; // 左儿子
right: Node | null; // 右儿子
}
很多人觉得树是一个很难的专题。实际上,只要你掌握了诀窍,它并没那么难。
从官方的难度标签来看,树的题目处于困难难度的一共是 14 道, 这其中还有 1 个标着树的标签但是却是图的题目,因此困难率是 13 / 175 ,也就是 7.4 % 左右。如果排除上锁的 5 道,困难的只有 9 道。大多数困难题,相信你看完本节的内容,也可以做出来。
从通过率来看,只有「不到三分之一」的题目平均通过率在 50% 以下,其他(绝大多数的题目)通过率都是 50%以上。50% 是一个什么概念呢?这其实很高了。举个例子来说, BFS 的平均通过率差不多在 50%。 而大家认为比较难的二分法和动态规划的平均通过率差不多 40%。
大家不要对树有压力, 树和链表一样是相对容易的专题,今天 lucifer 给大家带来了一个口诀「一个中心,两个基本点,三种题型,四个重要概念,七个技巧」,帮助你克服树这个难关。
一个中心指的是「树的遍历」。整个树的专题只有一个中心点,那就是树的遍历,大家务必牢牢记住。
不管是什么题目,核心就是树的遍历,这是一切的基础,不会树的遍历后面讲的都是白搭。
其实树的遍历的本质就是去把树里边儿的每个元素都访问一遍(任何数据结构的遍历不都是如此么?)。但怎么访问的?我不能直接访问叶子节点啊,我必须得从根节点开始访问,然后根据子节点指针访问子节点,但是子节点有多个(二叉树最多两个)方向,所以又有了先访问哪个的问题,这造成了不同的遍历方式。
?
左右子节点的访问顺序通常不重要,极个别情况下会有一些微妙区别。比如说我们想要访问一棵树的最左下角节点,那么顺序就会产生影响,但这种题目会比较少一点。
?
而遍历不是目的,遍历是为了更好地做处理,这里的处理包括搜索,修改树等。树虽然只能从根开始访问,但是我们可以「选择」在访问完毕回来的时候做处理,还是在访问回来之前做处理,这两种不同的方式就是「后序遍历」和「先序遍历」。
?
关于具体的遍历,后面会给大家详细讲,现在只要知道这些遍历是怎么来的就行了。
?
而树的遍历又可以分为两个基本类型,分别是深度优先遍历和广度优先遍历。这两种遍历方式并不是树特有的,但却伴随树的所有题目。值得注意的是,这两种遍历方式只是一种逻辑而已,因此理论可以应用于任何数据结构,比如 365. 水壶问题[5] 中,就可以对水壶的状态使用广度优先遍历,而水壶的状态可以用「一个二元组」来表示。
?
遗憾的是这道题的广度优先遍历解法在 LeetCode 上提交会超时
?
很多小朋友表示二叉树前中后序的递归写法没问题,但是迭代就写不出来,问我有什么好的方法没有。
这里就给大家介绍一种写迭代遍历树的实操技巧,统一三种树的遍历方式,包你不会错,这个方法叫做双色标记法。 如果你会了这个技巧,那么你平时练习大可「只用递归」。然后面试的时候,真的要求用迭代或者是对性能有特别要求的那种题目,那你就用我的方法套就行了,下面我来详细讲一下这种方法。
我们知道垃圾回收算法中,有一种算法叫三色标记法。 即:
那么我们可以模仿其思想,使用双色标记法来统一三种遍历。
其核心思想如下:
使用这种方法实现的中序遍历如下:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
可以看出,实现上 WHITE 就表示的是递归中的第一次进入过程,Gray 则表示递归中的从叶子节点返回的过程。 因此这种迭代的写法更接近递归写法的本质。
如要「实现前序、后序遍历,也只需要调整左右子节点的入栈顺序即可,其他部分是无需做任何变化」。
(前中后序遍历只需要调整这三句话的位置即可)
可以看出使用三色标记法,其写法类似递归的形式,因此便于记忆和书写。
有的同学可能会说,这里的每一个节点都会入栈出栈两次,相比普通的迭代入栈和出栈次数整整加了一倍,这性能可以接受么?我要说的是这种时间和空间的增加仅仅是常数项的增加,大多数情况并不会都程序造成太大的影响。 除了有时候比赛会比较恶心人,会「卡常」(卡常是指通过计算机原理相关的、与理论复杂度无关的方法对代码运行速度进行优化)。反过来看,大家写的代码大多数是递归,要知道递归由于内存栈的开销,性能通常比这里的二色标记法更差才对, 那为啥不用一次入栈的迭代呢?更极端一点,为啥大家不都用 morris 遍历 呢?
?
morris 遍历 是可以在常数的空间复杂度完成树的遍历的一种算法。
?
我认为在大多数情况下,大家对这种细小的差异可以不用太关注。另外如果这种遍历方式完全掌握了,再根据递归的思想去写一次入栈的迭代也不是难事。 无非就是调用函数的时候入栈,函数 return 时候出栈罢了。更多二叉树遍历的内容,大家也可以访问我之前写的专题《二叉树的遍历》[6]。
简单总结一下,树的题目一个中心就是树的遍历。树的遍历分为两种,分别是深度优先遍历和广度优先遍历。关于树的不同深度优先遍历(前序,中序和后序遍历)的迭代写法是大多数人容易犯错的地方,因此我介绍了一种统一三种遍历的方法 - 二色标记法,这样大家以后写迭代的树的前中后序遍历就再也不用怕了。如果大家彻底熟悉了这种写法,再去记忆和练习一次入栈甚至是 Morris 遍历即可。
其实用一次入栈和出栈的迭代实现递归也很简单,无非就是还是用递归思想,只不过你把递归体放到循环里边而已。大家可以在熟悉递归之后再回头看看就容易理解了。树的深度遍历的递归技巧,我们会在后面的《两个基本点》部分讲解。
上面提到了树的遍历有两种基本方式,分别是「深度优先遍历(以下简称 DFS)和广度优先遍历(以下简称 BFS),这就是两个基本点」。这两种遍历方式下面又会细分几种方式。比如 「DFS 细分为前中后序遍历, BFS 细分为带层的和不带层的」。
「DFS 适合做一些暴力枚举的题目,DFS 如果借助函数调用栈,则可以轻松地使用递归来实现。」
而 BFS 适合求最短距离,这个和层次遍历是不一样的,很多人搞混。这里强调一下,层次遍历和 BFS 是「完全不一样」的东西。
层次遍历就是一层层遍历树,按照树的层次顺序进行访问。
(层次遍历图示)
「BFS 的核心在于求最短问题时候可以提前终止,这才是它的核心价值,层次遍历是一种不需要提前终止的 BFS 的副产物」。这个提前终止不同于 DFS 的剪枝的提前终止,而是找到最近目标的提前终止。比如我要找距离最近的目标节点,BFS 找到目标节点就可以直接返回。而 DFS 要穷举所有可能才能找到最近的,这才是 BFS 的核心价值。实际上,我们也可以使用 DFS 实现层次遍历的效果,借助于递归,代码甚至会更简单。
?
如果找到任意一个满足条件的节点就好了,不必最近的,那么 DFS 和 BFS 没有太大差别。同时为了书写简单,我通常会选择 DFS。
?
以上就是两种遍历方式的简单介绍,下面我们对两者进行一个详细的讲解。
深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止,属于「盲目搜索」。
深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。因发明「深度优先搜索算法」,约翰 · 霍普克洛夫特与罗伯特 · 塔扬在 1986 年共同获得计算机领域的最高奖:图灵奖。
截止目前(2020-02-21),深度优先遍历在 LeetCode 中的题目是 129 道。在 LeetCode 中的题型绝对是超级大户了。而对于树的题目,我们基本上都可以使用 DFS 来解决,甚至我们可以基于 DFS 来做层次遍历,而且由于 DFS 可以基于递归去做,因此算法会更简洁。 在对性能有很高要求的场合,我建议你使用迭代,否则尽量使用递归,不仅写起来简单快速,还不容易出错。
DFS 图解:
binary-tree-traversal-dfs
(图片来自 https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search)
「这里的 stack 可以理解为自己实现的栈,也可以理解为调用栈。如果是调用栈的时候就是递归,如果是自己实现的栈的话就是迭代。」
一个典型的通用的 DFS 模板可能是这样的:
const visited = {}
function dfs(i) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
visited[i] = true // 将当前状态标为已搜索
for (根据i能到达的下个状态j) {
if (!visited[j]) { // 如果状态j没有被搜索过
dfs(j)
}
}
}
上面的 visited 是为了防止由于环的存在造成的死循环的。 而我们知道树是不存在环的,因此树的题目大多数不需要 visited,除非你对树的结构做了修改,比如就左子树的 left 指针指向自身,此时会有环。再比如 138. 复制带随机指针的链表 这道题需要记录已经复制的节点,这些需要记录 visited 信息的树的题目「少之又少」。
因此一个树的 DFS 更多是:
function dfs(root) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
for (const child of root.children) {
dfs(child)
}
}
而几乎所有的题目几乎都是二叉树,因此下面这个模板更常见。
function dfs(root) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
dfs(root.left)
dfs(root.right)
}
而我们不同的题目除了 if (满足特定条件部分不同之外),还会写一些特有的逻辑,这些逻辑写的位置不同,效果也截然不同。那么位置不同会有什么影响,什么时候应该写哪里呢?接下来,我们就聊聊两种常见的 DFS 方式。
前序遍历和后序遍历是最常见的两种 DFS 方式。而另外一种遍历方式 (中序遍历)一般用于平衡二叉树,这个我们后面的「四个重要概念」部分再讲。
如果你的代码大概是这么写的(注意主要逻辑的位置):
function dfs(root) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
// 主要逻辑
dfs(root.left)
dfs(root.right)
}
那么此时我们称为前序遍历。
而如果你的代码大概是这么写的(注意主要逻辑的位置):
function dfs(root) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
dfs(root.left)
dfs(root.right)
// 主要逻辑
}
那么此时我们称为后序遍历。
值得注意的是, 我们有时也会会写出这样的代码:
function dfs(root) {
if (满足特定条件){
// 返回结果 or 退出搜索空间
}
// 做一些事
dfs(root.left)
dfs(root.right)
// 做另外的事
}
如上代码,我们在进入和退出左右子树的时候分别执行了一些代码。那么这个时候,是前序遍历还是后续遍历呢?实际上,这属于混合遍历了。不过我们这里只考虑「主逻辑」的位置,关键词是「主逻辑」。
如果代码主逻辑在左右子树之前执行,那么就是前序遍历。如果代码主逻辑在左右子树之后执行,那么就是后序遍历。关于更详细的内容, 我会在「七个技巧」 中的「前后遍历」部分讲解,大家先留个印象,知道有着两种方式就好。
上面的《一个中心》部分,给大家介绍了一种干货技巧《双色遍历》统一三种遍历的迭代写法。 而树的遍历的递归的写法其实大多数人都没问题。为什么递归写的没问题,用栈写迭代就有问题呢? 本质上其实还是对递归的理解不够。那 lucifer 今天给大家介绍一种练习递归的技巧。其实文章开头也提到了,那就是画图 + 手动代入。有的同学不知道怎么画,这里我抛砖引玉分享一下我学习递归的画法。
比如我们要前序遍历一棵这样的树:
1
/ \
2 3
/ \
4 5
图画的还算比较清楚, 就不多解释了。大家遇到题目多画几次这样的递归图,慢慢就对递归有感觉了。
树的遍历的两种方式分别是 DFS 和 BFS,刚才的 DFS 我们简单过了一下前序和后序遍历,对它们有了一个简单印象。这一小节,我们来看下树的另外一种遍历方式 - BFS。
BFS 也是图论中算法的一种,不同于 DFS, BFS 采用横向搜索的方式,在数据结构上通常采用队列结构。 注意,DFS 我们借助的是栈来完成,而这里借助的是队列。
BFS 比较适合找「最短距离/路径」和「某一个距离的目标」。比如给定一个二叉树,在树的最后一行找到最左边的值。,此题是力扣 513 的原题。这不就是求距离根节点「最远距离」的目标么? 一个 BFS 模板就解决了。
BFS 图解:
binary-tree-traversal-bfs
(图片来自 https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search)
const visited = {}
function bfs() {
let q = new Queue()
q.push(初始状态)
while(q.length) {
let i = q.pop()
if (visited[i]) continue
if (i 是我们要找的目标) return 结果
for (i的可抵达状态j) {
if (j 合法) {
q.push(j)
}
}
}
return 没找到
}
BFS 我目前使用的模板就两种,这两个模板可以解决所有的树的 BFS 问题。
前面我提到了“BFS 比较适合找「最短距离/路径」和「某一个距离的目标」”。 如果我需要求的是最短距离/路径,我是不关心我走到第几步的,这个时候可是用不标记层的目标。而如果我需要求距离某个节点距离等于 k 的所有节点,这个时候第几步这个信息就值得被记录了。
?
小于 k 或者 大于 k 也是同理。
?
一个常见的 BFS 模板,代入题目只需要根据题目微调即可。
class Solution:
def bfs(k):
# 使用双端队列,而不是数组。因为数组从头部删除元素的时间复杂度为 N,双端队列的底层实现其实是链表。
queue = collections.deque([root])
# 记录层数
steps = 0
# 需要返回的节点
ans = []
# 队列不空,生命不止!
while queue:
size = len(queue)
# 遍历当前层的所有节点
for _ in range(size):
node = queue.popleft()
if (step == k) ans.append(node)
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
# 遍历完当前层所有的节点后 steps + 1
steps += 1
return ans
不带层的模板更简单,因此大家其实只需要掌握带层信息的目标就够了。
一个常见的 BFS 模板,代入题目只需要根据题目微调即可。
class Solution:
def bfs(k):
# 使用双端队列,而不是数组。因为数组从头部删除元素的时间复杂度为 N,双端队列的底层实现其实是链表。
queue = collections.deque([root])
# 队列不空,生命不止!
while queue:
node = queue.popleft()
# 由于没有记录 steps,因此我们肯定是不需要根据层的信息去判断的。否则就用带层的模板了。
if (node 是我们要找到的) return node
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
return -1
以上就是 BFS 的两种基本方式,即带层和不带层,具体使用哪种看题目是否需要根据层信息做判断即可。
树的遍历是后面所有内容的基础,而树的遍历的两种方式 DFS 和 BFS 到这里就简单告一段落,现在大家只要知道 DFS 和 BFS 分别有两种常见的方式就够了,后面我会给大家详细补充。
树的题目就三种类型,分别是:「搜索类,构建类和修改类,而这三类题型的比例也是逐渐降低的」,即搜索类的题目最多,其次是构建类,最后是修改类。这一点和链表有很大的不同,链表更多的是修改类。
接下来,lucifer 给大家逐一讲解这三种题型。
搜索类的题目是树的题目的绝对大头。而搜索类只有两种解法,那就是 DFS 和 BFS,下面分别介绍。
几乎所有的搜索类题目都可以方便地使用递归来实现,关于递归的技巧会在「七个技巧中的单/双递归」部分讲解。还有一小部分使用递归不好实现,我们可以使用 BFS,借助队列轻松实现,比如最经典的是求二叉树任意两点的距离,树的距离其实就是最短距离,因此可以用 BFS 模板解决。这也是为啥我说「DFS 和 BFS」是树的题目的两个基本点的原因。
所有搜索类的题目只要把握三个核心点,即「开始点」,「结束点」 和 「目标」即可。
DFS 搜索类的基本套路就是从入口开始做 dfs,然后在 dfs 内部判断是否是结束点,这个结束点通常是「叶子节点」或「空节点」,关于结束这个话题我们放在「七个技巧中的边界」部分介绍,如果目标是一个基本值(比如数字)直接返回或者使用一个全局变量记录即可,如果是一个数组,则可以通过扩展参数的技巧来完成,关于扩展参数,会在「七个技巧中的参数扩展」部分介绍。 这基本就是搜索问题的全部了,当你读完后面的七个技巧,回头再回来看这个会更清晰。
套路模板:
# 其中 path 是树的路径, 如果需要就带上,不需要就不带
def dfs(root, path):
# 空节点
if not root: return
# 叶子节点
if not root.left and not root.right: return
path.append(root)
# 逻辑可以写这里,此时是前序遍历
dfs(root.left)
dfs(root.right)
# 需要弹出,不然会错误计算。
# 比如对于如下树:
"""
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
"""
# 如果不 pop,那么 5 -> 4 -> 11 -> 2 这条路径会变成 5 -> 4 -> 11 -> 7 -> 2,其 7 被错误地添加到了 path
path.pop()
# 逻辑也可以写这里,此时是后序遍历
return 你想返回的数据
比如剑指 Offer 34. 二叉树中和为某一值的路径 这道题,题目是:输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 这不就是从根节点开始,到叶子节点结束的所有路径「搜索出来」,挑选出和为目标值的路径么?这里的开始点是根节点, 结束点是叶子节点,目标就是路径。
对于求这种满足「特定和」的题目,我们都可以方便地使用「前序遍历 + 参数扩展的形式」,关于这个,我会在「七个技巧中的前后序部分」展开。
?
由于需要找到所有的路径,而不仅仅是一条,因此这里适合使用回溯暴力枚举。关于回溯,可以参考我的 回溯专题[7]
?
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
def backtrack(nodes, path, cur, remain):
# 空节点
if not cur: return
# 叶子节点
if cur and not cur.left and not cur.right:
if remain == cur.val:
res.append((path + [cur.val]).copy())
return
# 选择
tepathmp.append(cur.val)
# 递归左右子树
backtrack(nodes, path, cur.left, remain - cur.val)
backtrack(nodes, path, cur.right, remain - cur.val)
# 撤销选择
path.pop(-1)
ans = []
# 入口,路径,目标值全部传进去,其中路径和path都是扩展的参数
dfs(ans, [], root, target, )
return ans
再比如:1372. 二叉树中的最长交错路径,题目描述:
给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:
选择二叉树中 任意 节点和一个方向(左或者右)。
如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。
改变前进方向:左变右或者右变左。
重复第二步和第三步,直到你在树中无法继续移动。
交错路径的长度定义为:访问过的节点数目 - 1(单个节点的路径长度为 0 )。
请你返回给定树中最长 交错路径 的长度。
比如:
此时需要返回 3
解释:蓝色节点为树中最长交错路径(右 -> 左 -> 右)。
这不就是从任意节点「开始」,到任意节点「结束」的所有交错「路径」全部「搜索出来」,挑选出最长的么?这里的开始点是树中的任意节点,结束点也是任意节点,目标就是最长的交错路径。
对于入口是任意节点的题目,我们都可以方便地使用「双递归」来完成,关于这个,我会在「七个技巧中的单/双递归部分」展开。
对于这种交错类的题目,一个好用的技巧是使用 -1 和 1 来记录方向,这样我们就可以通过乘以 -1 得到另外一个方向。
?
886. 可能的二分法 和 785. 判断二分图 都用了这个技巧。
?
用代码表示就是:
next_direction = cur_direction * - 1
这里我们使用双递归即可解决。 如果题目限定了只从根节点开始,那就可以用单递归解决了。值得注意的是,这里内部递归需要 cache 一下 , 不然容易因为重复计算导致超时。
?
我的代码是 Python,这里的 lru_cache 就是一个缓存,大家可以使用自己语言的字典模拟实现。
?
class Solution:
@lru_cache(None)
def dfs(self, root, dir):
if not root:
return 0
if dir == -1:
return int(root.left != None) + self.dfs(root.left, dir * -1)
return int(root.right != None) + self.dfs(root.right, dir * -1)
def longestZigZag(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.dfs(root, 1), self.dfs(root, -1), self.longestZigZag(root.left), self.longestZigZag(root.right))
这个代码不懂没关系,大家只有知道搜索类题目的大方向即可,具体做法我们后面会介绍,大家留个印象就行。更多的题目以及这些技巧的详细使用方式放在「七个技巧部分」展开。
这种类型相比 DFS,题目数量明显降低,套路也少很多。题目大多是求距离,套用我上面的两种 BFS 模板基本都可以轻松解决,这个不多介绍了。
除了搜索类,另外一个大头是构建类。构建类又分为两种:普通二叉树的构建和二叉搜索树的构建。
而普通二叉树的构建又分为三种:
?
这种题目假设输入的遍历的序列中都不含重复的数字,想想这是为什么。
?
最经典的就是 剑指 Offer 37. 序列化二叉树。我们知道力扣的所有的树表示都是使用数字来表示的,而这个数组就是一棵树的层次遍历结果,部分叶子节点的子节点(空节点)也会被打印。比如:[1,2,3,null,null,4,5],就表示的是如下的一颗二叉树:
我们是如何根据这样的一个层次遍历结果构造出原始二叉树的呢?这其实就属于构造二叉树的内容,这个类型目前力扣就这一道题。这道题如果你彻底理解 BFS,那么就难不倒你。
除了这种静态构建,还有一种很很罕见的动态构建二叉树的,比如 894. 所有可能的满二叉树 ,对于这个题,直接 BFS 就好了。由于这种题很少,因此不做多的介绍。大家只要把最核心的掌握了,这种东西自然水到渠成。
普通二叉树无法根据一种序列重构的原因是只知道根节点,无法区分左右子树。如果是二叉搜索树,那么就有可能根据「一种遍历序列」构造出来。 原因就在于二叉搜索树的根节点的值大于所有的左子树的值,且小于所有的右子树的值。因此我们可以根据这一特性去确定左右子树的位置,经过这样的转换就和上面的普通二叉树没有啥区别了。比如 1008. 前序遍历构造二叉搜索树
上面介绍了两种常见的题型:搜索类和构建类。还有一种比例相对比较小的题目类型是修改类。
?
当然修改类的题目也是要基于搜索算法的,不找到目标怎么删呢?
?
修改类的题目有两种基本类型。
由于头条的发文限制字数,因此剩下的贴不了,大家可以去我的公众号《力扣加加》解锁全部内容
我整理的 1000 多页的电子书已经开发下载了,大家可以去我的公众号《力扣加加》后台回复电子书获取。
[1]
树标签: https://leetcode-cn.com/tag/tree/
[2]
leetcode 算法题解: https://github.com/azl397985856/leetcode
[3]
递归可视化网站: https://recursion.now.sh/
[4]
平衡二叉树: https://github.com/azl397985856/leetcode/blob/master/thinkings/balanced-tree.md
[5]
365. 水壶问题: https://github.com/azl397985856/leetcode/blob/master/problems/365.water-and-jug-problem.md
[6]
二叉树的遍历: https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md
[7]
回溯专题: https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md
[8]
113. 路径总和 I: https://github.com/azl397985856/leetcode/blob/master/problems/113.path-sum-ii.md
[9]
几乎刷完了力扣所有的链表题,我发现了这些东西。。。: https://lucifer.ren/blog/2020/11/08/linked-list/
*请认真填写需求信息,我们会在24小时内与您取得联系。