同學(xué)，二叉樹的各種遍歷方式，我都幫你總結(jié)了，附有隊(duì)列堆棧圖解（鞏固基礎(chǔ)，強(qiáng)烈建議收藏）

靚仔靚女們大家好，今天我來分享一篇關(guān)于二叉樹的文章（建議收藏，便于鞏固基礎(chǔ)）。

• 看完此文leetcode至少解決八道題
• 掌握二叉樹的前序、中序、后序遍歷以及兩種不同的實(shí)現(xiàn)方式：遞歸與非遞歸
• 非遞歸時(shí)遍歷與層次遍歷時(shí)，有詳細(xì)的圖解表示隊(duì)列/棧中的元素是如何移動(dòng)的，有助于理解代碼的運(yùn)行

二叉樹介紹

二叉樹（binary tree） 是指樹中節(jié)點(diǎn)的度不大于2的有序樹，它是一種最簡單且最重要的樹。

二叉樹的遞歸定義為： 二叉樹是一棵空樹，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹

• 邏輯上二叉樹有五種基本形態(tài)，如圖所示
1. 空二叉樹
2. 只有一個(gè)根結(jié)點(diǎn)的二叉樹
3. 只有左子樹
4. 完全二叉樹
5. 只有右子樹

二叉樹相關(guān)屬性解釋：

• 結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹分支的信息。
• 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹的數(shù)目稱為結(jié)點(diǎn)的度。
• 葉子結(jié)點(diǎn)：也稱為終端結(jié)點(diǎn)，沒有子樹的結(jié)點(diǎn)或者度為零的結(jié)點(diǎn)。
• 分支結(jié)點(diǎn)：也稱為非終端結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)。
• 樹的度：樹中所有結(jié)點(diǎn)的度的最大值。
• 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始，假設(shè)根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的子節(jié)點(diǎn)為第2層，依此類推，如果某一個(gè)結(jié)點(diǎn)位于第L層，則其子節(jié)點(diǎn)位于第L+1層。
• 樹的深度：也稱為樹的高度，樹中所有結(jié)點(diǎn)的層次最大值稱為樹的深度。
• 有序樹：如果樹中各棵子樹的次序是有先后次序，則稱該樹為有序樹。
• 無序樹：如果樹中各棵子樹的次序沒有先后次序，則稱該樹為無序樹。

二叉樹遍歷方式

• 二叉樹遍歷方式分為三種
• 前序遍歷（根左右）：訪問根結(jié)點(diǎn)，再訪問左子樹、再訪問右子樹。
• 中序遍歷（左根右）：先訪問左子樹，再訪問根結(jié)點(diǎn)、再訪問右子樹。
• 后續(xù)遍歷（左右根）：先訪問左子樹，再訪問右子樹，再訪問根結(jié)點(diǎn)。

例如一個(gè)這個(gè)樣子的二叉樹，按三種遍歷方法分別遍歷，輸出的結(jié)果分別是

• 前序遍歷：ABDECFG
• 中序遍歷：DBEAFCG
• 后續(xù)遍歷：DEBFGCA

下面我們一起來用代碼實(shí)現(xiàn)下這三種遍歷

• 注：以上前序、中序、后序每一種遍歷方式都有遞歸和非遞歸兩種實(shí)現(xiàn)方法
• 前序遍歷就是深度優(yōu)先遍歷（DFS）
• 層次遍歷就是廣度優(yōu)先遍歷（BFS）

二叉樹遞歸遍歷

* 前序遍歷 （LeetCode ?144）

class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?preorderTraversal(TreeNode?root)?{
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中????
????????list.add(root.val);
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷左子樹
????????if?(root.left?!=?null){
????????????preorderTraversal(root.left);
????????}
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷右子樹
????????if?(root.right?!=?null){
????????????preorderTraversal(root.right);
????????}
????????//最后返回列表
????????return?list;
????}
}

• 中序遍歷（LeetCode ?94）

class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?inorderTraversal(TreeNode?root)?{
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹
????????if?(root.left?!=?null){
????????????inorderTraversal(root.left);
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中
????????list.add(root.val);
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹
????????if?(root.right?!=?null){
????????????inorderTraversal(root.right);
????????}
????????//最后返回列表
????????return?list;
????}
}

• 后續(xù)遍歷（LeetCode ?145）

class?Solution?{
????//聲明列表
????ArrayList?list?=?new?ArrayList<>();
????public?List?postorderTraversal(TreeNode?root)?{
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹
????????if?(root.left?!=?null){
????????????postorderTraversal(root.left);
????????}
????????//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹
????????if?(root.right?!=?null){
????????????postorderTraversal(root.right);
????????}
????????//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中
????????list.add(root.val);
????????//最后返回列表
????????return?list;
????}
}

我們通過觀察發(fā)現(xiàn)，這代碼怎么這么像，是的就是很像，他們唯一的區(qū)別就是list.add(root.val);代碼的位置不一樣，這行代碼就代表文中的 遍歷（訪問）
下圖中為前序遍歷（根左右）

下圖中為中序遍歷（左根右）

下圖中為后序遍歷（左右根）

二叉樹非遞歸遍歷

• 用到棧（FILO 先進(jìn)后出的特性）
• 每段代碼后，都有棧和其中元素的關(guān)系具體過程，建議靜下心來慢慢看，有助于理解代碼如何運(yùn)行

• 前序遍歷

class?Solution?{
????List?list?=???new?ArrayList();
????public?List?preorderTraversal(TreeNode?root)?{
????????//如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if(root==null){
????????????return??new?ArrayList();
????????}
????????//聲明一個(gè)棧
????????Stack?stack?=?new?Stack<>();
????????//將節(jié)點(diǎn)入棧
????????stack.push(root);
????????//如果棧不為空
????????while?(!stack.empty()){
????????????//從棧彈出這個(gè)節(jié)點(diǎn)
????????????TreeNode?node?=?stack.pop();
????????????//添加進(jìn)列表中
????????????list.add(node.val);
????????????//?如果這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空
????????????if?(node.right!=null){
????????????????//?將其入棧??因?yàn)闂Ｊ窍冗M(jìn)后出，所以先壓棧右子節(jié)點(diǎn)??后出
????????????????stack.push(node.right);
????????????}
????????????//?如果這個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空
????????????if?(node.left!=null){
????????????????//?將其入棧?因?yàn)闂Ｊ窍冗M(jìn)后出，所以后壓棧左子節(jié)點(diǎn)?先出
????????????}
????????}
????????//返回列表
????????return?list;
????}
}

• 中序遍歷

class?Solution?{
????public?List?inorderTraversal(TreeNode?root)?{
????????//判斷節(jié)點(diǎn)是否為空，為空的話直接返回空列表
????????if?(root?==?null){
????????????return?new?ArrayList();
????????}
????????//聲明列表存儲(chǔ)結(jié)果
????????List?list?=??new?ArrayList();
????????//聲明一個(gè)棧
????????Stack?stack?=?new?Stack<>();
????????//當(dāng)節(jié)點(diǎn)不為空或者棧不為空時(shí)
????????while?(root?!=?null?||?!stack.empty()){
????????????//當(dāng)節(jié)點(diǎn)不為空時(shí)
????????????while?(root?!=?null){
????????????????//將節(jié)點(diǎn)壓棧
????????????????stack.push(root);
????????????????//將節(jié)點(diǎn)指向其左子節(jié)點(diǎn)
????????????????root?=?root.left;
????????????}
????????????//如果棧不為空
????????????if?(!stack.empty()){
????????????????//將棧里元素彈出來
????????????????TreeNode?node?=?stack.pop();
????????????????//添加進(jìn)列表中
????????????????list.add(node.val);
????????????????//將節(jié)點(diǎn)指向其右子節(jié)點(diǎn)
????????????????root?=?node.right;
????????????}
????????}
????????return?list;
????}
}

• 后序遍歷

class?Solution?{
????public?List?postorderTraversal(TreeNode?root)?{
????????//?如果根節(jié)點(diǎn)為空，則直接返回空列表
????????if?(root?==?null){
????????????return??new?ArrayList<>();
????????}
????????//聲明列表
????????ArrayList?list?=?new?ArrayList<>();
????????//聲明棧A
????????Stack?stackA?=?new?Stack();
????????//聲明棧B
????????Stack?stackB?=?new?Stack();
????????//將次元素壓入棧A
????????stackA.push(root);
????????//當(dāng)棧A不為空時(shí)
????????while?(!stackA.empty()){
????????????//取出其中壓入的元素
????????????TreeNode?node?=?stackA.pop();
????????????//壓入棧B中
????????????stackB.push(node);
????????????//當(dāng)此節(jié)點(diǎn)左子節(jié)點(diǎn)不為空時(shí)
????????????if?(node.left?!=?null){
????????????????//壓入棧A
????????????????stackA.push(node.left);
????????????}
????????????//當(dāng)此節(jié)點(diǎn)右子節(jié)點(diǎn)不為空時(shí)
????????????if?(node.right?!=?null){
????????????????//壓入棧A
????????????????stackA.push(node.right);
????????????}
????????}
????????//當(dāng)棧B不為空時(shí)
????????while?(!stackB.empty()){
????????????//取出其元素并且添加至列表中
????????????TreeNode?node?=?stackB.pop();
????????????list.add(node.val);
????????}
????????//最后返回列表
????????return?list;
????}
}

二叉樹層序遍歷（BFS）

• LeetCode ?102 ? 二叉樹的層序遍歷
• 用到隊(duì)列（FIFO 先進(jìn)先出的特性）代碼后有隊(duì)列和其中元素的關(guān)系具體過程，建議靜下心來慢慢看，有助于理解代碼如何運(yùn)行

class?Solution?{
????public?List>?levelOrder(TreeNode?root)?{
????????if?(root?==?null)?{
????????????return?new?ArrayList>();
????????}
????????//?聲明一個(gè)列表存儲(chǔ)每一行的數(shù)據(jù)
????????List>?result?=?new?ArrayList<>();
????????//聲明一個(gè)隊(duì)列
????????LinkedList?queue?=?new?LinkedList<>();
????????//如果根節(jié)點(diǎn)不為空，將其入隊(duì)
????????queue.offer(root);
????????//當(dāng)隊(duì)列不為空時(shí)，代表隊(duì)列里有數(shù)據(jù)
????????while?(!queue.isEmpty())?{
????????????//存儲(chǔ)每一行的數(shù)據(jù)line
????????????List?line?=?new?ArrayList();
????????????//保存隊(duì)列中現(xiàn)有數(shù)據(jù)的個(gè)數(shù)，這些就是要添加至每一行列表的值
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????//取出隊(duì)列的節(jié)點(diǎn)?（FIFO?先進(jìn)先出）
????????????TreeNode?node?=?queue.poll();
????????????line.add(node.val);
??????????????if?(node.left?!=?null)?{
??????????????????queue.offer(node.left);
??????????????}
??????????????if?(node.right?!=?null)?{
??????????????????queue.offer(node.right);
??????????????}
????????????}
????????????result.add(line);
????????}
????????return?result;
????}
}

leetcode二叉樹相關(guān)練習(xí)

• 我們看到了這里，對(duì)二叉樹的前序（DFS）、中序、后序、遞歸/非遞歸以及層次遍歷(BFS)都有了一定的了解（如果上面的圖都消化了的話）

然后我們趁熱打鐵來幾道leetcode題目試試手?。傮w代碼和上面只有稍微的改動(dòng)，因?yàn)榇笾滤枷胧且粯拥?，把上面的?nèi)容都消化了的話就很簡單啦）

• leetcode-257 二叉樹的所有路徑

class?Solution?{
????public?List?binaryTreePaths(TreeNode?root)?{
????????if?(root?==?null){
????????????return?new?ArrayList<>();
????????}
????????ArrayList?list?=?new?ArrayList<>();
????????Stack?stack?=?new?Stack();
????????//這個(gè)棧存儲(chǔ)路徑，與上一個(gè)存儲(chǔ)節(jié)點(diǎn)的棧一樣的操作
????????Stack?path?=?new?Stack();
????????stack.push(root);
????????path.push(root.val+"");
????????while?(!stack.empty()){
????????????TreeNode?node?=?stack.pop();
????????????String?p?=?path.pop();
????????????//當(dāng)是葉子節(jié)點(diǎn)的時(shí)候，此時(shí)棧中的路徑即為一條完整的路徑，可以加入到結(jié)果中
????????????if?(node.right?==?null?&&?node.left?==?null?){
????????????????list.add(p);
????????????}
????????????//如果右子節(jié)點(diǎn)不為空
????????????if?(node.right?!=?null){
????????????????stack.push(node.right);
????????????????//將臨時(shí)路徑繼續(xù)壓棧
????????????????path.push(p+"->"+node.right.val);
????????????}
????????????//如果左子節(jié)點(diǎn)不為空
????????????if?(node.left?!=?null){
????????????????stack.push(node.left);
????????????????//將臨時(shí)路徑繼續(xù)壓棧
????????????????path.push(p+"->"+node.left.val);
????????????}
????????}
????????return?list;
????}
}

• leetcode-104 二叉樹的最大深度 與 劍指offer 55-I 相同

class?Solution?{
????public?int?maxDepth(TreeNode?root)?{
???????if?(root?==?null){
???????????return?0;
???????}
????????LinkedList?queue?=?new?LinkedList<>();
????????int?result?=?0;
????????queue.offer(root);
????????while?(!queue.isEmpty()){
????????????//層數(shù)+1
????????????result++;
????????????//這是當(dāng)前層的節(jié)點(diǎn)的個(gè)數(shù)
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????????//要將其全部出隊(duì)后，才可以再次計(jì)數(shù)
????????????????TreeNode?node?=?queue.poll();
????????????????if?(node.left?!=?null){
????????????????????//如果出隊(duì)的節(jié)點(diǎn)還有左子節(jié)點(diǎn)，就入隊(duì)
????????????????????queue.offer(node.left);
????????????????}
????????????????if?(node.right?!=?null){
????????????????????//如果出隊(duì)的節(jié)點(diǎn)還有右子節(jié)點(diǎn)，就入隊(duì)
????????????????????queue.offer(node.right);
????????????????}
????????????}
????????}
????????//返回層數(shù)
????????return?result;

????}
}

• leetcode-107 二叉樹的層序遍歷2

class?Solution?{
????public?List>?levelOrderBottom(TreeNode?root)?{
????????if?(root?==?null){
????????????return?new?ArrayList>()?;
????????}
????????List>?result?=?new?ArrayList>()?;
????????LinkedList?queue?=?new?LinkedList<>();
????????//聲明一個(gè)棧，用來存儲(chǔ)每一層的節(jié)點(diǎn)
????????Stack?>?stack?=?new?Stack<>();
????????queue.offer(root);
????????while?(!queue.isEmpty()){
????????????int?size?=?queue.size();
????????????ArrayList?list?=?new?ArrayList<>();
????????????for?(int?i=0;i????????????????TreeNode?node?=?queue.poll();
????????????????list.add(node.val);
????????????????if?(node.left?!=?null){
????????????????????queue.offer(node.left);
????????????????}
????????????????if?(node.right?!=?null){
????????????????????queue.offer(node.right);
????????????????}
????????????}
????????????//將這一層的節(jié)點(diǎn)壓入棧中
????????????stack.push(list);
????????}
????????//當(dāng)棧不為空時(shí)，彈出結(jié)果，從而達(dá)到從下往上遍歷二叉樹的效果
????????while?(!stack.isEmpty()){
????????????ArrayList?list?=?stack.pop();
????????????result.add(list);
????????}
????????return?result;
????}
}

總結(jié)

我們通過這篇文章，至少可以解決leetcode上以下幾道題目

• 前序遍歷 （LeetCode ?144）

• 中序遍歷（LeetCode ?94）

• 后續(xù)遍歷（LeetCode ?145）

• LeetCode ?102 ? 二叉樹的層序遍歷

• leetcode-257 二叉樹的所有路徑

• leetcode-104 二叉樹的最大深度 與 劍指offer 55-I 相同

• leetcode-107 二叉樹的層序遍歷2

• 來個(gè)直擊靈魂的三連吧！