二叉樹的各種遍歷方式，我都幫你總結了，附有隊列堆棧圖解

今天我來分享一篇關于二叉樹的文章（建議收藏，便于鞏固基礎）。

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

二叉樹介紹

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

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

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

二叉樹相關屬性解釋：

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

二叉樹遍歷方式

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

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

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

下面我們一起來用代碼實現下這三種遍歷

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

二叉樹遞歸遍歷

* 前序遍歷 （LeetCode ?144）

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

• 中序遍歷（LeetCode ?94）

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

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

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

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

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

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

二叉樹非遞歸遍歷

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

• 前序遍歷

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

• 中序遍歷

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

• 后序遍歷

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

二叉樹層序遍歷（BFS）

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

class?Solution?{
????public?List>?levelOrder(TreeNode?root)?{
????????if?(root?==?null)?{
????????????return?new?ArrayList>();
????????}
????????//?聲明一個列表存儲每一行的數據
????????List>?result?=?new?ArrayList<>();
????????//聲明一個隊列
????????LinkedList?queue?=?new?LinkedList<>();
????????//如果根節(jié)點不為空，將其入隊
????????queue.offer(root);
????????//當隊列不為空時，代表隊列里有數據
????????while?(!queue.isEmpty())?{
????????????//存儲每一行的數據line
????????????List?line?=?new?ArrayList();
????????????//保存隊列中現有數據的個數，這些就是要添加至每一行列表的值
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????//取出隊列的節(jié)點?（FIFO?先進先出）
????????????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二叉樹相關練習

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

然后我們趁熱打鐵來幾道leetcode題目試試手！（總體代碼和上面只有稍微的改動，因為大致思想是一樣的，把上面的內容都消化了的話就很簡單啦）

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

class?Solution?{
????public?List?binaryTreePaths(TreeNode?root)?{
????????if?(root?==?null){
????????????return?new?ArrayList<>();
????????}
????????ArrayList?list?=?new?ArrayList<>();
????????Stack?stack?=?new?Stack();
????????//這個棧存儲路徑，與上一個存儲節(jié)點的棧一樣的操作
????????Stack?path?=?new?Stack();
????????stack.push(root);
????????path.push(root.val+"");
????????while?(!stack.empty()){
????????????TreeNode?node?=?stack.pop();
????????????String?p?=?path.pop();
????????????//當是葉子節(jié)點的時候，此時棧中的路徑即為一條完整的路徑，可以加入到結果中
????????????if?(node.right?==?null?&&?node.left?==?null?){
????????????????list.add(p);
????????????}
????????????//如果右子節(jié)點不為空
????????????if?(node.right?!=?null){
????????????????stack.push(node.right);
????????????????//將臨時路徑繼續(xù)壓棧
????????????????path.push(p+"->"+node.right.val);
????????????}
????????????//如果左子節(jié)點不為空
????????????if?(node.left?!=?null){
????????????????stack.push(node.left);
????????????????//將臨時路徑繼續(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()){
????????????//層數+1
????????????result++;
????????????//這是當前層的節(jié)點的個數
????????????int?size?=?queue.size();
????????????for?(int?i=0;i????????????????//要將其全部出隊后，才可以再次計數
????????????????TreeNode?node?=?queue.poll();
????????????????if?(node.left?!=?null){
????????????????????//如果出隊的節(jié)點還有左子節(jié)點，就入隊
????????????????????queue.offer(node.left);
????????????????}
????????????????if?(node.right?!=?null){
????????????????????//如果出隊的節(jié)點還有右子節(jié)點，就入隊
????????????????????queue.offer(node.right);
????????????????}
????????????}
????????}
????????//返回層數
????????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<>();
????????//聲明一個棧，用來存儲每一層的節(jié)點
????????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é)點壓入棧中
????????????stack.push(list);
????????}
????????//當棧不為空時，彈出結果，從而達到從下往上遍歷二叉樹的效果
????????while?(!stack.isEmpty()){
????????????ArrayList?list?=?stack.pop();
????????????result.add(list);
????????}
????????return?result;
????}
}

推薦關注