聊聊從上到下打印二叉樹
作者：程序員千羽
最差情況下，即當樹為平衡二叉樹時，最多有 N/2 個樹節點同時在 queue 中，使用 O(N) 大小的額外空間。
Leetcode :
- I：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
- II：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
- III：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_25_levelOrder/Solution.java
從上到下打印二叉樹 I
“題目描述 ：從上到下打印出二叉樹的每個節點，同一層的節點按照從左到右的順序打印。例如：給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回：
- [3,9,20,15,7]
提示：節點總數 <= 1000
解題思路：
- 題目要求的二叉樹的 從上至下 打印(即按層打印)，又稱為二叉樹的 廣度優先搜索(BFS)。
- BFS 通常借助 隊列 的先入先出特性來實現。
算法流程：
- 特例處理： 當樹的根節點為空，則直接返回空列表 [] ;
- 初始化： 打印結果列表 res = [] ，包含根節點的隊列 queue = [root] ;
- BFS 循環： 當隊列 queue 為空時跳出;
- 出隊： 隊首元素出隊，記為 node;
- 打印： 將 node.val 添加至列表 tmp 尾部;
- 添加子節點： 若 node 的左(右)子節點不為空，則將左(右)子節點加入隊列 queue ;
- 返回值： 返回打印結果列表 res 即可。
復雜度分析：
- 時間復雜度 O(N)： N為二叉樹的節點數量，即 BFS 需循環 N次。
- 空間復雜度 O(N) ：最差情況下，即當樹為平衡二叉樹時，最多有 N/2 個樹節點同時在 queue 中，使用 O(N) 大小的額外空間。
- package com.nateshao.sword_offer.topic_25_levelOrder;
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.Queue;
- /**
- * @date Created by 邵桐杰 on 2021/11/29 14:57
- * @微信公眾號 程序員千羽
- * @個人網站 www.nateshao.cn
- * @博客 https://nateshao.gitee.io
- * @GitHub https://github.com/nateshao
- * @Gitee https://gitee.com/nateshao
- * Description: 從上到下打印二叉樹 思路：利用隊列（鏈表）輔助實現。
- *
- * add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
- * remove 移除并返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
- * element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
- * offer 添加一個元素并返回true 如果隊列已滿，則返回false
- * poll 移除并返問隊列頭部的元素 如果隊列為空，則返回null
- * peek 返回隊列頭部的元素 如果隊列為空，則返回null
- * put 添加一個元素 如果隊列滿，則阻塞
- * take 移除并返回隊列頭部的元素 如果隊列為空，則阻塞
- */
- public class Solution {
- /**
- * 隊列
- *
- * @param root
- * @return
- */
- public int[] levelOrder(TreeNode root) {
- if (root == null) return new int[0];//空樹則返回空數組
- ArrayList<Integer> list = new ArrayList<>();// 申請一個動態數組 ArrayList 動態添加節點值
- Queue<TreeNode> queue = new LinkedList<>();
- queue.offer(root);// 根結點先入隊
- while (!queue.isEmpty()) {
- TreeNode node = queue.poll();// 取出當前隊首元素
- list.add(node.val);
- if (node.left != null) queue.offer(node.left);// 左子節點入隊
- if (node.right != null) queue.offer(node.right);// 右子節點入隊
- }
- // 將 ArrayList 轉為 int數組并返回
- int[] res = new int[list.size()];
- for (int i = 0; i < res.length; i++) {
- res[i] = list.get(i);
- }
- return res;
- }
- /************ 遞歸 *************/
- public ArrayList<Integer> PrintFromTopToBottom2(TreeNode root) {
- ArrayList<Integer> list = new ArrayList<Integer>();
- if (root == null) {
- return list;
- }
- list.add(root.val);
- levelOrder(root, list);
- return list;
- }
- public void levelOrder(TreeNode root, ArrayList<Integer> list) {
- if (root == null) {
- return;
- }
- if (root.left != null) {
- list.add(root.left.val);
- }
- if (root.right != null) {
- list.add(root.right.val);
- }
- levelOrder(root.left, list);
- levelOrder(root.right, list);
- }
- public class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) {
- val = x;
- }
- }
- }
從上到下打印二叉樹 II
題目描述 ：從上到下按層打印二叉樹，同一層的節點按從左到右的順序打印，每一層打印到一行。
“例如：給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回其層次遍歷結果：
- [
- [3],
- [9,20],
- [15,7]
- ]
- 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);
- }
- res.add(tmp);
- }
- return res;
- }
III. 從上到下打印二叉樹 III
“題目描述： 請實現一個函數按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。例如: 給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回其層次遍歷結果：
- [
- [3],
- [20,9],
- [15,7]
- ]
- 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;
- }
- }
參考連接：
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5
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
責任編輯：武曉燕
來源：
程序員千羽
