【問題描述】[中等]

請實現一個函數按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。 例如: 給定二叉樹: [3,9,20,null,null,15,7],3/ \9 20/ \15 7 返回其層次遍歷結果： [[3],[20,9],[15,7] ]提示：節點總數 <= 1000

【解答思路】

1. 層序遍歷 + 倒序

時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if(root != null) queue.add(root);while(!queue.isEmpty()) {List<Integer> tmp = new ArrayList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();tmp.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}if(res.size() % 2 == 1) Collections.reverse(tmp);res.add(tmp);}return res;} }

2. 層序遍歷 + 雙端隊列

時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if(root != null) queue.add(root);while(!queue.isEmpty()) {LinkedList<Integer> tmp = new LinkedList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶數層 -> 隊列頭部else tmp.addFirst(node.val); // 奇數層 -> 隊列尾部if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}res.add(tmp);}return res;} }

3. 層序遍歷 + 雙端隊列（奇偶層邏輯分離）

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> deque = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if(root != null) deque.add(root);while(!deque.isEmpty()) {// 打印奇數層List<Integer> tmp = new ArrayList<>();for(int i = deque.size(); i > 0; i--) {// 從左向右打印TreeNode node = deque.removeFirst();tmp.add(node.val);// 先左后右加入下層節點if(node.left != null) deque.addLast(node.left);if(node.right != null) deque.addLast(node.right);}res.add(tmp);if(deque.isEmpty()) break; // 若為空則提前跳出// 打印偶數層tmp = new ArrayList<>();for(int i = deque.size(); i > 0; i--) {// 從右向左打印TreeNode node = deque.removeLast();tmp.add(node.val);// 先右后左加入下層節點if(node.right != null) deque.addFirst(node.right);if(node.left != null) deque.addFirst(node.left);}res.add(tmp);}return res;} }

【總結】

1.細節

1.1 Queue
新建

// Queue<TreeNode> queue= new LinkedList<>();//queue.add(root);Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};

入隊出隊 add(x) poll()

1.2 ArrayList
新建
ArrayList ans = new ArrayList<>();
長度 size（）
獲取元素 get(i)

2. Queue

Queue是在兩端出入的List，所以也可以用數組或鏈表來實現。

• add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
• remove 移除并返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
• element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
• offer 添加一個元素并返回true 如果隊列已滿，則返回false
• poll 移除并返問隊列頭部的元素 如果隊列為空，則返回null
• peek 返回隊列頭部的元素 如果隊列為空，則返回null
• put 添加一個元素 如果隊列滿，則阻塞
• take 移除并返回隊列頭部的元素 如果隊列為空，則阻塞

注意

• remove、element、offer 、poll、peek 其實是屬于Queue接口。

• add remove element操作在隊滿或者隊空的時候會報異常。

• offer poll peek 在隊滿或者隊空的時候不會報異常。

• put take操作屬于阻塞操作。隊滿隊空均會阻塞。

3.LinkedList

• 以雙向鏈表實現的LinkedList既是List，也是Queue。
• 它是唯一一個允許放入null的Queue。

4.BFS 層次遍歷 隊列實現

轉載鏈接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er–3/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[32-3]题[从上到下打印二叉树 ][BFS]的全部內容，希望文章能夠幫你解決所遇到的問題。

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