廢話不多說，喊一句號子鼓勵自己：程序員永不失業(yè)，程序員走向架構(gòu)！本篇Blog的主題是【二叉樹的遍歷】，使用【二叉樹】這個基本的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，這個高頻題的站點是：CodeTop，篩選條件為：目標公司+最近一年+出現(xiàn)頻率排序，由高到低的去?？蚑OP101去找，只有兩個地方都出現(xiàn)過才做這道題（CodeTop本身匯聚了LeetCode的來源），確保刷的題都是高頻要面試考的題。
就著這兩個高頻題目把二叉樹的遍歷類型題目刷一遍
名曲目標題后，附上題目鏈接，后期可以依據(jù)解題思路反復快速練習，題目按照題干的基本數(shù)據(jù)結(jié)構(gòu)分類，且每個分類的第一篇必定是對基礎數(shù)據(jù)結(jié)構(gòu)的介紹。
二叉樹的前序遍歷【EASY】
前序、中序、后序都有迭代和遞歸的實現(xiàn)方式
題干
解題思路
前序遍歷簡單來說就是“根左右”，展開來說就是對于一顆二叉樹優(yōu)先訪問其根節(jié)點，然后訪問它的左子樹，等左子樹全部訪問完了再訪問其右子樹，而對于子樹也按照之前的訪問方式，直到到達葉子節(jié)點，每次訪問一個節(jié)點之后，它的左子樹是一個要前序遍歷的子問題，它的右子樹同樣是一個要前序遍歷的子問題。那我們可以用遞歸處理：
- 終止條件： 當子問題到達葉子節(jié)點后，后一個不管左右都是空，因此遇到空節(jié)點就返回。
- 返回值： 每次處理完子問題后，就是將子問題訪問過的元素返回，依次存入了數(shù)組中。
- 本級任務： 每個子問題優(yōu)先訪問這棵子樹的根節(jié)點，然后遞歸進入左子樹和右子樹。
具體做法：
step 1：準備數(shù)組用來記錄遍歷到的節(jié)點值，Java可以用List
step 2：從根節(jié)點開始進入遞歸，遇到空節(jié)點就返回，否則將該節(jié)點值加入數(shù)組。
step 3：依次進入左右子樹進行遞歸。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：遞歸、DFS
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param root TreeNode類
* @return int整型一維數(shù)組
*/
public int[] preorderTraversal (TreeNode root) {
// 1 定義用來返回的數(shù)據(jù)
List<Integer> list = new ArrayList<>();
// 2 遞歸填充list的值
preorder(list, root);
// 3 返回結(jié)果處理
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
private void preorder(List<Integer> list, TreeNode root) {
// 1 遞歸終止條件
if (root == null) {
return;
}
// 2 按順序遞歸填充左右子樹
list.add(root.val);
preorder(list, root.left);
preorder(list, root.right);
}
}
復雜度分析
時間復雜度：遍歷了N個節(jié)點，所以時間復雜度為O（N）
空間復雜度：最壞情況下，樹退化為鏈表，遞歸棧深度為N，所以空間復雜度為O（N）
二叉樹的中序遍歷【EASY】
換位中序遍歷
題干
解題思路
如果一棵二叉樹，對于每個根節(jié)點都優(yōu)先訪問左子樹，那結(jié)果是什么？從根節(jié)點開始不斷往左，第一個被訪問的肯定是最左邊的節(jié)點。然后訪問該節(jié)點的右子樹，最后向上回到父問題。因為每次訪問最左的元素不止對一整棵二叉樹成立，而是對所有子問題都成立，因此循環(huán)的時候自然最開始都是遍歷到最左，然后訪問，然后再進入右子樹，我們可以用棧來實現(xiàn)回歸父問題
- 尋找最左子樹，此過程逐層將樹及左子樹的根節(jié)點壓入棧中，把要后處理的上層子樹根節(jié)點先壓入操作棧
- 棧頂即當前最左子樹根節(jié)點，也是上層子樹的左子節(jié)點，將值放入到list
- 節(jié)點指針移動到當前指針右節(jié)點，如果右節(jié)點為空，則本層處理完成，棧再彈出上層節(jié)點，接著循環(huán)處理
其實思路與遞歸就相似了，只不過將遞歸棧具象化了
代碼實現(xiàn)
遞歸的思路和代碼不再贅述，直接給出
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param root TreeNode類
* @return int整型一維數(shù)組
*/
public int[] inorderTraversal (TreeNode root) {
// 1 定義入?yún)⒑头祷刂?/span>
List<Integer> list = new ArrayList<>();
// 2 中序遞歸獲取list
inorder(list, root);
// 3 list結(jié)果轉(zhuǎn)換
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
private void inorder(List<Integer> list, TreeNode root) {
// 1 終止條件
if (root == null) {
return;
}
inorder(list, root.left);
list.add(root.val);
inorder(list, root.right);
}
}
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：棧、DFS
算法：迭代
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param root TreeNode類
* @return int整型一維數(shù)組
*/
public int[] inorderTraversal (TreeNode root) {
// 1 定義入?yún)⒑洼o助棧
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) {
return new int[0];
}
// 2 尋找最左子樹
TreeNode tempRoot = root;
while (tempRoot != null || !stack.isEmpty()) {
// 2-1 尋找最左子樹，此過程逐層將樹及左子樹的根節(jié)點壓入棧中
while (tempRoot != null) {
// 把要后處理的上層子樹根節(jié)點先壓入操作棧
stack.push(tempRoot);
tempRoot = tempRoot.left;
}
// 2-2 棧頂即當前最左子樹根節(jié)點，也是上層子樹的左子節(jié)點
TreeNode node = stack.pop();
list.add(node.val);
// 2-3 節(jié)點指針移動到當前指針右節(jié)點，如果右節(jié)點為空，則本層處理完成，棧再彈出上層節(jié)點
tempRoot = node.right;
}
// 3 list結(jié)果轉(zhuǎn)換
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
復雜度分析
時間復雜度：遍歷了N個節(jié)點，所以時間復雜度為O（N）
空間復雜度：最壞情況下，樹退化為鏈表，輔助遞歸棧深度為N，所以空間復雜度為O（N）
二叉樹的后序遍歷【EASY】
ok，再來看二叉樹的后序遍歷
題干
解題思路
左右根，同前序遍歷及中序遍歷的遞歸解法，不再贅述
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：遞歸、DFS
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param root TreeNode類
* @return int整型一維數(shù)組
*/
public int[] postorderTraversal (TreeNode root) {
// 1 定義用來返回的數(shù)據(jù)
List<Integer> list = new ArrayList<>();
// 2 遞歸填充list的值
postorder(list, root);
// 3 返回結(jié)果處理
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
private void postorder(List<Integer> list, TreeNode root) {
if (root == null) {
return;
}
postorder(list, root.left);
postorder(list, root.right);
list.add(root.val);
}
}
復雜度分析
時間復雜度：遍歷了N個節(jié)點，所以時間復雜度為O（N）
空間復雜度：最壞情況下，樹退化為鏈表，遞歸棧深度為N，所以空間復雜度為O（N）
二叉樹的層序遍歷【MID】
二叉樹的層序遍歷
題干
解題思路
二叉樹的層次遍歷就是按照從上到下每行，然后每行中從左到右依次遍歷，得到的二叉樹的元素值。對于層次遍歷，我們通常會使用隊列來輔助：
因為隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，我們依照它的性質(zhì)，如果從左到右訪問完一行節(jié)點，并在訪問的時候依次把它們的子節(jié)點加入隊列，那么它們的子節(jié)點也是從左到右的次序，且排在本行節(jié)點的后面，因此隊列中出現(xiàn)的順序正好也是從左到右，正好符合層次遍歷的特點
- step 1：首先判斷二叉樹是否為空，空樹沒有遍歷結(jié)果。
- step 2：建立輔助隊列，根節(jié)點首先進入隊列。不管層次怎么訪問，根節(jié)點一定是第一個，那它肯定排在隊伍的最前面。
- step 3：每次進入一層，統(tǒng)計隊列中元素的個數(shù)。因為每當訪問完一層，下一層作為這一層的子節(jié)點，一定都加入隊列，而再下一層還沒有加入，因此此時隊列中的元素個數(shù)就是這一層的元素個數(shù)。
- step 4：每次遍歷一層的節(jié)點數(shù)，將其依次從隊列中彈出，然后加入這一行的一維數(shù)組中，如果它們有子節(jié)點，依次加入隊列排隊等待訪問。
- step 5：訪問完這一層的元素后，將這個一維數(shù)組加入二維數(shù)組中，再訪問下一層。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：隊列
算法：迭代、BFS
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param root TreeNode類
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// 1 定義要返回的數(shù)據(jù)結(jié)構(gòu)
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
// 2 定義輔助隊列結(jié)構(gòu)，每次隊列都只存一層
Queue<TreeNode> queue = new LinkedList<TreeNode>();
// 3 首先將第一層也就是根節(jié)點放入隊列
if (root == null) {
return new ArrayList<>();
}
queue.add(root);
// 4 核心處理邏輯，分層獲取元素并加入列表
while (!queue.isEmpty()) {
ArrayList<Integer> levelList = new ArrayList<Integer>();
// 需要用一個臨時變量承接隊列大小，否則每次新加一層永遠無法遍歷完本層
int queueSize = queue.size();
for (int i = 0; i < queueSize; i++) {
// 4-1 獲取隊首元素，當前層元素，并添加到層列表中
TreeNode node = queue.poll();
levelList.add(node.val);
// 4-2 分別將節(jié)點左右元素添加到隊列尾部
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// 4-3 將本層元素集合添加到結(jié)果集中
result.add(levelList);
}
return result;
}
}
復雜度分析
時間復雜度：遍歷了一遍樹，時間復雜度為O（N）
空間復雜度：使用了輔助隊列，空間復雜度為O（N）
二叉樹的鋸齒形層序遍歷【MID】
難度升級，每層要反過來
題干
解題思路
解題思路與層次遍歷相同，只不過需要隔行反轉(zhuǎn)。只需增加標志位即可。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：隊列
算法：迭代、BFS
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param pRoot TreeNode類
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
// 1 定義返回結(jié)果
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (pRoot == null) {
return new ArrayList<>();
}
// 2 定義隊列，并將根節(jié)點放入
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
// 3 設置反轉(zhuǎn)標志位，隔行反轉(zhuǎn)
boolean isReverse = false;
// 4 核心邏輯，將數(shù)據(jù)放入結(jié)果集
while (!queue.isEmpty()) {
int queueSize = queue.size();
ArrayList<Integer> levelList = new ArrayList<Integer>();
for (int i = 0; i < queueSize; i++ ) {
TreeNode node = queue.poll();
levelList.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// 依據(jù)標志位結(jié)果進行層級數(shù)據(jù)反轉(zhuǎn)
if (isReverse) {
Collections.reverse(levelList);
}
// 重置標志位，以便下一層反轉(zhuǎn)
isReverse = !isReverse;
result.add(levelList);
}
return result;
}
}
復雜度分析
時間復雜度：遍歷了一遍樹，時間復雜度為O（N）
空間復雜度：使用了輔助隊列，空間復雜度為O（N）
二叉樹的右視圖【MID】
使用深度優(yōu)先搜素方法
題干
解題思路
我們可以對二叉樹進行層次遍歷，那么對于每層來說，最右邊的結(jié)點一定是最后被遍歷到的。二叉樹的層次遍歷可以用廣度優(yōu)先搜索實現(xiàn)。
- 執(zhí)行廣度優(yōu)先搜索，左結(jié)點排在右結(jié)點之前，這樣，我們對每一層都從左到右訪問。因此，只保留每個深度最后訪問的結(jié)點，我們就可以在遍歷完整棵樹后得到每個深度最右的結(jié)點
所以只要按照層序遍歷的思路，把每一層的最后一個節(jié)點放到結(jié)果集就行了。
代碼實現(xiàn)
給出代碼實現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：隊列
算法：迭代、BFS
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：
- 10 個數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動窗口、中心擴散
當然包括但不限于以上
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
* 求二叉樹的右視圖
* @param root 樹的根節(jié)點
* @param inOrder int整型一維數(shù)組 中序遍歷
* @return int整型一維數(shù)組
*/
public List<Integer> rightSideView(TreeNode root) {
// 1 定義返回的結(jié)果集
List<Integer> result = new ArrayList<Integer>();
if (root == null) {
return new ArrayList<Integer>();
}
// 2 定義隊列，用來容納每一層節(jié)點
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
// 3 遍歷每一層并獲取最右邊的節(jié)點
while (!queue.isEmpty()) {
int queueSize = queue.size();
for (int i = 0; i < queueSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
// 如果節(jié)點是本層最后一個節(jié)點，則添加到結(jié)果集中
if (i == queueSize - 1) {
result.add(node.val);
}
}
}
return result;
}
}
復雜度分析
時間復雜度： O(N)，每個節(jié)點都入隊出隊了 1 次。
空間復雜度： O(N)，使用了額外的隊列空間。
拓展知識：深度優(yōu)先遍歷和廣度優(yōu)先遍歷
廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）是兩種經(jīng)典的圖遍歷算法，它們也可以用于二叉樹的遍歷和搜索。以下是它們的定義以及在二叉樹中的應用場景：
廣度優(yōu)先搜索（BFS）：
BFS是一種圖遍歷算法，它從一個起始節(jié)點開始，逐層地遍歷與該節(jié)點相鄰的節(jié)點，然后再遍歷與這些相鄰節(jié)點相鄰的節(jié)點，以此類推。BFS通常使用隊列數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。
在二叉樹中的應用場景：文章來源：http://www.zghlxwxcb.cn/news/detail-733127.html
- 層級遍歷：BFS可以用于按層級遍歷二叉樹，從根節(jié)點開始，逐層遍歷，可以方便地實現(xiàn)層級順序的操作。
- 查找最小深度：BFS可以用于查找二叉樹的最小深度，即從根節(jié)點到最近葉子節(jié)點的最短路徑。
- 查找特定元素：如果您需要在二叉樹中查找特定元素，BFS可以用于在樹中搜索，一旦找到目標元素，就可以停止搜索。
- 判斷是否為完全二叉樹：BFS可以用于判斷二叉樹是否是完全二叉樹，通過觀察層級遍歷的結(jié)果，可以檢查每一層是否都填滿節(jié)點。
深度優(yōu)先搜索（DFS）：
DFS是一種圖遍歷算法，它從一個起始節(jié)點開始，沿著一條路徑一直深入到無法繼續(xù)前進的節(jié)點，然后返回上一層，繼續(xù)探索其他路徑。DFS通常使用遞歸函數(shù)或顯式的棧數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。
在二叉樹中的應用場景：
- 前序遍歷：DFS通常用于前序遍歷二叉樹，即先訪問根節(jié)點，然后遞歸地訪問左子樹和右子樹。前序遍歷用于深度優(yōu)先搜索問題。
- 中序遍歷：DFS也可以用于中序遍歷二叉樹，即先遞歸地訪問左子樹，然后訪問根節(jié)點，最后遞歸地訪問右子樹。中序遍歷在二叉搜索樹中用于獲取有序元素。
- 后序遍歷：DFS還可用于后序遍歷二叉樹，即先遞歸地訪問左子樹和右子樹，最后訪問根節(jié)點。后序遍歷在某些問題中很有用，例如計算表達式的值或查找樹的高度。
總的來說，BFS適用于需要層級遍歷或查找最短路徑的問題，而DFS適用于需要深度優(yōu)先搜索或?qū)涞慕Y(jié)構(gòu)進行更復雜操作的問題。在二叉樹中，您可以根據(jù)具體問題的要求選擇使用BFS或DFS。有時，問題可能需要同時使用這兩種方法以解決不同的子問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-733127.html
到了這里，關于【算法訓練-二叉樹 一】【遍歷二叉樹】前序遍歷、中序遍歷、后續(xù)遍歷、層序遍歷、鋸齒形層序遍歷、二叉樹右視圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
