整合營銷服務商
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
克爾樹是區塊鏈技術的一個基本概念。它們是一種特殊的二進制樹，用于編碼大塊的信息。默克爾樹的酷之處在于，它們是一種自下而上的 "建立"，并允許你驗證某些值是否存在于樹中，而不需要在樹的每個元素上循環。正如我們會看到的，這可能非常有用。
默克爾樹是一種哈希樹，其中每個葉子節點都標有數據塊的加密哈希值，而每個非葉子節點都標有其子節點的加密哈希值的標簽。大多數哈希樹的實現是二進制的（每個節點有兩個子節點），但它們也可以有更多的子節點。
一個典型的默克爾樹看起來是這樣的。
(引用自 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 hardhatnpm install --save-dev @nomiclabs/hardhat-waffle ethereum-waffle chai @nomiclabs/hardhat-ethers ethers
npx hardhat現在您的Hardhat文件夾已設置完畢。
我們還需要安裝一些額外的依賴項來執行一切。因此，再次在指向根目錄的終端中執行以下命令：
npm install @openzeppelin/contracts keccak256 merkletreejscontracts現在首先在您的文件夾中創建一個名為的文件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元素
表示頁面中的一個內容區塊,比如章節、頁眉、頁腳或頁面的其他部分?？梢院蚳1、 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 如果借助函數調用棧，則可以輕松地使用遞歸來實現?！?/span>
而 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 可以理解為自己實現的棧，也可以理解為調用棧。如果是調用棧的時候就是遞歸，如果是自己實現的棧的話就是迭代?！?/span>
一個典型的通用的 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小時內與您取得聯系。
