LeetCode——樹：層次遍歷、前中后序遍歷

---

目錄

層次遍歷

二叉樹的層平均值

找樹左下角的值

前中后序遍歷

概述

非遞歸實現二叉樹的前序遍歷

非遞歸實現二叉樹的中序遍歷

非遞歸實現二叉樹的后序遍歷

---

1. 層次遍歷

1. 二叉樹的層平均值（LeetCode637）

概述
1. 給定一個非空二叉樹, 返回一個由每層節點平均值組成的數組.

思路

利用廣度優先搜索遍歷整顆二叉樹。

首先將它的根節點放入隊列queue中，如果queue不為null，進入while循環
1. 計算當前queue的size用于待會for循環遍歷，創建變量sum記錄每層的和
2. queue.size.for循環，創建臨時節點node存儲queue彈出的元素，sum+=node.val。如果node.left或者right不為null，則加入隊列
3. 退出for循環，則得到了每層的值sum，該層節點個數cnt。相除即是結果

代碼

public static List < Double > averageOfLevels(TreeNode root) {List<Double> ret = new ArrayList<>();if (root==null){return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){int cnt = queue.size();double sum = 0;for (int i = 0; i < cnt; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left !=null)queue.offer(node.left);if (node.right!=null)queue.offer(node.right);}ret.add(sum/cnt);}return ret;}

小結
1. 利用隊列可以先遍歷每一層的節點

---

2. 找樹左下角的值（LeetCode513）

概述
1. 給定一個二叉樹，在樹的最后一行找到最左邊的值。

思路

利用隊列進行層次遍歷，遍歷過程加入隊列時，先加右節點，再加左節點，這樣隊列每層出來的順序就從右到左的

如果遍歷加入隊列時，是先加左節點，再加右節點，那么隊列每層出來的順序就是從左往右的

代碼

public static int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {root = queue.poll();if (root.right != null)queue.offer(root.right);if (root.left != null)queue.offer(root.left);}return root.val;}

---

3. 前中后序遍歷

0. 概述

1. 層次遍歷順序：[1,2,3,4,5,6]
2. 前序遍歷順序：[1,2,4,5,3,6]
3. 中序遍歷順序：[4,2,5,1,3,6]
4. 后序遍歷順序：[4,5,2,6,3,1]

層次遍歷使用BFS實現，利用的就是BFS一層一層遍歷的特性

而前序，中序，后序遍歷利用了DFS實現。前序，中序，后序只是對節點訪問的順序有一點不同，其他都相同

遞歸版前序，中序，后序代碼

public static void preOrderRecur(TreeNode head) {if (head == null) {return;}System.out.print(head.val + " ");preOrderRecur(head.left);preOrderRecur(head.right);}public static void inOrderRecur(TreeNode head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.val + " ");inOrderRecur(head.right);}public static void posOrderRecur(TreeNode head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.val + " ");}

1. 非遞歸實現二叉樹的前序遍歷

利用棧

利用棧先進后出的數據結構，可以對二叉樹進行遍歷。

先把head節點加入stack，當stack不為null時while循環stack，彈出棧頂元素，打印（因為前序遍歷的順序是：根左右，第一次遇到這個節點就打印）。

然后如果當前節點右孩子不為null，加入棧，左孩子不為null，加入棧，因為打印順序是：根左右，所以加入順序為根右左

代碼實現

public static void preOrderUnRecur(TreeNode head) {if (head==null){return;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.isEmpty()){head = stack.pop();System.out.print(head.val+" ");if (head.right!=null)stack.push(head.right);if (head.left!=null)stack.push(head.left);}}

2. 非遞歸實現二叉樹的中序遍歷

利用棧

當棧不為null或者head!=null時，如果此時head!=null，則將它加入棧中，也就是將左邊節點全部壓入棧中

當head==null時，就會返回棧的最后一個元素，此時是第二次到達這個節點，所以就要打印（中序遍歷：左中右，表示第二遇到這個節點就打印），然后跳到右節點

代碼實現

public static void inOrderUnRecur(TreeNode head) {if (head != null) {Stack<TreeNode> stack = new Stack<>();while (!stack.isEmpty() || head != null) {if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();System.out.print(head.val + " ");head = head.right;}}}}

3. 非遞歸實現二叉樹的后序遍歷

利用雙棧

后序遍歷的順序為：左右中，我們知道前序遍歷：中左右，當我們在前序遍歷時先添加左節點，再添加右節點時，它的順序就會變為中右左（棧的特性），這是我們將元素添加到另一個棧，打印出的順序就為：左右中

代碼實現

public static void posOrderUnRecur1(TreeNode head) {if (head!=null){Stack<TreeNode> s1 = new Stack<>();Stack<TreeNode> s2 = new Stack<>();s1.push(head);while (!s1.isEmpty()){head = s1.pop();s2.push(head);if (head.left!=null)s1.push(head.left);if (head.right!=null)s1.push(head.right);}while (!s2.isEmpty()){System.out.print(s2.pop().val+" ");}}}

---

補充：還有一種神奇的二叉樹前中后序遍歷算法——Morris遍歷，有時間補充，之前總結過了，不過我也有點忘了…
二叉樹的遍歷（遞歸，非遞歸，Morris）

總結

以上是生活随笔為你收集整理的LeetCode——树：层次遍历、前中后序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。