• 二叉樹的遞歸遍歷
• 二叉樹的非遞歸遍歷寫法
• 層序遍歷

---

遞歸怎么寫？

按照三要素可以保證寫出正確的遞歸算法：

1.確定遞歸函數的參數和返回值： 確定哪些參數是遞歸的過程中需要處理的，那么就在遞歸函數里加上這個參數， 并且還要明確每次遞歸的返回值是什么進而確定遞歸函數的返回類型。

2.確定終止條件： 寫完了遞歸算法, 運行的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統也是用一個棧的結構來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出。

3.確定單層遞歸的邏輯： 確定每一層遞歸需要處理的信息。在這里也就會重復調用自己來實現遞歸的過程。

---

前置必會

一定要會自己寫出樹的類定義

public class TreeNode{TreeNode left;TreeNode right;int val;TreeNode(){}TreeNode(int val){this.val = val}TreeNode(int val,TreeNode right,TreeNode left){this.val = val;this.left = left;this.right = right;
}

144.二叉樹的前序遍歷

遞歸寫法

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();dfs(root,result);return result;}void dfs(TreeNode root,List<Integer> result){if(root==null){return;}result.add(root.val);dfs(root.left,result);dfs(root.right,result);}}

非遞歸寫法：
我認為就是記思路。
1.用一個棧作為輔助。
2.前序遍歷是根左右，每次先處理的是中間節點，那么先將根節點放入棧中，然后將右孩子加入棧，再加入左孩子。之所以是反過來是因為，這樣出棧的時候才是根左右的順序。直接來看圖模擬

即每次在處理根節點的時候，將根節點出隊，然后將其右孩子先進棧，再將左孩子進棧。
這樣進行處理之后，出棧的結果就會是前序遍歷的結果。

如果還是不懂，我建議直接結合代碼，然后結合上面圖，記下來這個做法。我覺得這個直接想是不好想的。

非遞歸其實就是用輔助數據結構，配合循環

class Solution {public List<Integer> preorderTraversal(TreeNode root) {//結果集List<Integer> result = new ArrayList<>();//特判if(root == null){return result;}//創建輔助棧Deque<TreeNode> st = new ArrayDeque<>();//根節點先入棧st.push(root);//當棧不空的時候while(!st.isEmpty()){//先處理根節點，即將根節點出棧。這就對應著根TreeNode node = st.pop();//將出棧的根節點加入結果集result.add(node.val);//先將右節點加入棧中，可以這么想，早點加入，那么就晚點出。所以右節點出的時候，要比左節點晚，那么這里出也就是和上面節點出棧一個道理。所以這里就完成了根左右里面的根左。因為左節點進的晚，出的就早。if(node.right!=null){st.push(node.right);}//然后才是到左節點，晚點進就可以早點出。if(node.left!=null){st.push(node.left);}}return result;}
}

這是我第二寫總結的流程：
1.初始化：
創建一個空的結果列表
創建一個輔助棧
將根節點壓入棧中

2.主循環： 當棧不為空時，執行以下操作：

a. 處理當前節點：
從棧中彈出一個節點
將該節點的值添加到結果列表中

b. 壓入子節點：
如果該節點有右子節點，將右子節點壓入棧中
如果該節點有左子節點，將左子節點壓入棧中
返回結果列表

這種方法的關鍵點在于：
根節點最先被處理，這符合前序遍歷的"根-左-右"順序。
右子節點先于左子節點入棧，這確保了左子節點會先于右子節點被處理。
這種非遞歸方法的優點是：

避免了遞歸調用的開銷
對于深度很大的樹，可以防止棧溢出
實現簡單，易于理解
與中序遍歷的非遞歸方法相比，前序遍歷的非遞歸實現更為直觀，因為它可以直接按照遍歷順序處理節點，而不需要像中序遍歷那樣先到達最左節點。

145.二叉樹的后序遍歷

遞歸寫法

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result  = new ArrayList<>();dfs(root,result);return result;}public void dfs(TreeNode root,List<Integer> result){if(root==null){return;}dfs(root.left,result);dfs(root.right,result);result.add(root.val);}
}

非遞歸寫法：
這個解法是一個技巧解。
由于前序遍歷是根左右，而后續遍歷是左右根。所以如果調整一下前序遍歷的順序，先加左節點，再加右節點，那么得到的結果就是按根右左規則得到的。所以此時做翻轉，那么得到的結果就是按左右根得到的結果。與后序遍歷的結果不謀而合。
所以解法就是線序遍歷調整左右入棧方式，然后再對最終結果做翻轉。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {Deque<TreeNode> st = new ArrayDeque<>();List<Integer> result = new ArrayList<>();if(root==null){return result;}st.push(root);while(!st.isEmpty()){TreeNode node = st.pop();result.add(node.val);if(node.left!=null){st.push(node.left);}if(node.right!=null){st.push(node.right);}}Collections.reverse(result);return result;}
}

94.二叉樹的中序遍歷

遞歸寫法

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();dfs(root,result);return result;}public void dfs(TreeNode root,List<Integer> result){if(root==null){return;}dfs(root.left,result);result.add(root.val);dfs(root.right,result);}
}

非遞歸寫法：
看這個圖，然后結合圖片，記下這個做法：

1.初始化：
創建一個空的結果列表和一個空的棧
將當前節點設置為根節點

2.主循環： 當當前節點不為空或棧不為空時，執行以下操作：

a. 左子樹遍歷：
如果當前節點不為空
將當前節點壓入棧
移動到左子節點

b. 節點處理：
如果當前節點為空（即已經到達最左端）
從棧中彈出一個節點
將該節點的值添加到結果列表中
將當前節點移動到右子節點

3.返回結果列表

這種方法模擬了遞歸的過程：

首先盡可能深入地遍歷左子樹
然后處理節點本身
最后遍歷右子樹
使用棧來保存已經遍歷過的父節點，以便在處理完左子樹后能夠回溯。

還是按代碼思維走一遍，又和自己想的還是有一點區別。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {//結果集List<Integer> result = new ArrayList<>();//特判if(root==null){return result;}//輔助棧Deque<TreeNode> st = new ArrayDeque<>();//用一個遍歷指針指向rootTreeNode cur = root;//這里就是進遞歸處理的邏輯，循環條件決定了能不能遞歸處理下去。//cur!=null表明這個元素不空，可以進棧，!st.isEmpty()，是用來回溯的，表明棧中還有走過的元素需要進行處理。所以棧中走過的元素沒處理完也要繼續處理。while(cur!=null || !st.isEmpty()){//根據中序，左根右的走法，需要一路向最左下走。走的過程就一直入棧，保存之前的狀態。如果cur==null，說明走到最左下的節點的左分支上了，也就是null。if(cur!=null){st.push(cur);cur = cur.left;}else{//不能繼續往左走了才處理這里，這里就是開始回溯，回溯一下回到最左下的節點，此節點并不是null。那就把這個元素出棧，把這個元素的val加入結果集。由于每個元素都要左根右，這里處理了根節點，那還要往右節點走。下一波顯然cur還是null，那么此時就會彈出沿著路線返回的根節點，往后都是這樣。注意是依靠彈出的節點進行轉移，因為棧里面的節點才是記錄先前的狀態，別自己瞎寫一個。cur = st.pop();result.add(cur.val);cur = cur.right;}}//當st里面為空的時候，就是所有節點都處理完的時候。return result;}
}

---

102.二叉樹的層序遍歷

用隊列。
看一個圖就懂了。
隊列先進先出，符合一層一層遍歷的邏輯。
下面的代碼就是二叉樹層序遍歷的模板題，會這個模板，之后遇到只要是層序遍歷的題，隨便殺。

總的來說，這個解法看完，里面的len的處理我是當時沒想到的。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();checkFun(root,result);return result;}public void checkFun(TreeNode node,List<List<Integer>> result){//特判if(node==null){return;}//輔助隊列Deque<TreeNode> que = new ArrayDeque<>();//根節點先入隊que.offerLast(node);//隊列不空就代表流程還沒有結束while(!que.isEmpty()){//記錄一層元素的結果集List<Integer> itemList = new ArrayList<Integer>();//在一開始先記錄長度，該長度即隊列目前的長度，就是該層元素的個數。//記錄len就是為了做一個界限，即處理完這一層元素后，就要收集一次結果集。int len = que.size();//這個循環做依次將該層元素出隊，并擴展其左右節點加入隊列當中。while(len>0){//先出隊TreeNode tmpNode = que.pollFirst();//加入結果集itemList.add(tmpNode.val);//擴展左右節點，加入隊列中。if(tmpNode.left!=null){que.offerLast(tmpNode.left);}if(tmpNode.right!=null){que.offerLast(tmpNode.right);}//做完之后該層元素數量要-1len--;}//處理完一層后記錄一次結果。result.add(itemList);}}
}

---

107.二叉樹的層序遍歷Ⅱ

在上題的基礎上將結果集翻轉就結束了。

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();checkFun(root,result);Collections.reverse(result);return result;}public void checkFun(TreeNode node,List<List<Integer>> result){if(node==null){return;}Deque<TreeNode> que = new ArrayDeque<>();que.offerLast(node);while(!que.isEmpty()){List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while(len>0){TreeNode tmpNode = que.pollFirst();itemList.add(tmpNode.val);if(tmpNode.left!=null){que.offerLast(tmpNode.left);}if(tmpNode.right!=null){que.offerLast(tmpNode.right);}len--;}result.add(itemList);}}
}