聊聊從上到下打印二叉樹
作者：程序員千羽
最差情況下，即當(dāng)樹為平衡二叉樹時(shí)，最多有 N/2 個(gè)樹節(jié)點(diǎn)同時(shí)在 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
“題目描述 ：從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。例如：給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回：
- [3,9,20,15,7]
提示：節(jié)點(diǎn)總數(shù) <= 1000
解題思路：
- 題目要求的二叉樹的 從上至下 打印(即按層打印)，又稱為二叉樹的 廣度優(yōu)先搜索(BFS)。
- BFS 通常借助 隊(duì)列 的先入先出特性來實(shí)現(xiàn)。
算法流程：
- 特例處理： 當(dāng)樹的根節(jié)點(diǎn)為空，則直接返回空列表 [] ;
- 初始化： 打印結(jié)果列表 res = [] ，包含根節(jié)點(diǎn)的隊(duì)列 queue = [root] ;
- BFS 循環(huán)： 當(dāng)隊(duì)列 queue 為空時(shí)跳出;
- 出隊(duì)： 隊(duì)首元素出隊(duì)，記為 node;
- 打印： 將 node.val 添加至列表 tmp 尾部;
- 添加子節(jié)點(diǎn)： 若 node 的左(右)子節(jié)點(diǎn)不為空，則將左(右)子節(jié)點(diǎn)加入隊(duì)列 queue ;
- 返回值： 返回打印結(jié)果列表 res 即可。
復(fù)雜度分析：
- 時(shí)間復(fù)雜度 O(N)： N為二叉樹的節(jié)點(diǎn)數(shù)量，即 BFS 需循環(huán) N次。
- 空間復(fù)雜度 O(N) ：最差情況下，即當(dāng)樹為平衡二叉樹時(shí)，最多有 N/2 個(gè)樹節(jié)點(diǎn)同時(shí)在 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
- * @微信公眾號(hào) 程序員千羽
- * @個(gè)人網(wǎng)站 www.nateshao.cn
- * @博客 https://nateshao.gitee.io
- * @GitHub https://github.com/nateshao
- * @Gitee https://gitee.com/nateshao
- * Description: 從上到下打印二叉樹 思路：利用隊(duì)列（鏈表）輔助實(shí)現(xiàn)。
- *
- * add 增加一個(gè)元索 如果隊(duì)列已滿，則拋出一個(gè)IIIegaISlabEepeplian異常
- * remove 移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常
- * element 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常
- * offer 添加一個(gè)元素并返回true 如果隊(duì)列已滿，則返回false
- * poll 移除并返問隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
- * peek 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
- * put 添加一個(gè)元素 如果隊(duì)列滿，則阻塞
- * take 移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則阻塞
- */
- public class Solution {
- /**
- * 隊(duì)列
- *
- * @param root
- * @return
- */
- public int[] levelOrder(TreeNode root) {
- if (root == null) return new int[0];//空樹則返回空數(shù)組
- ArrayList<Integer> list = new ArrayList<>();// 申請(qǐng)一個(gè)動(dòng)態(tài)數(shù)組 ArrayList 動(dòng)態(tài)添加節(jié)點(diǎn)值
- Queue<TreeNode> queue = new LinkedList<>();
- queue.offer(root);// 根結(jié)點(diǎn)先入隊(duì)
- while (!queue.isEmpty()) {
- TreeNode node = queue.poll();// 取出當(dāng)前隊(duì)首元素
- list.add(node.val);
- if (node.left != null) queue.offer(node.left);// 左子節(jié)點(diǎn)入隊(duì)
- if (node.right != null) queue.offer(node.right);// 右子節(jié)點(diǎn)入隊(duì)
- }
- // 將 ArrayList 轉(zhuǎn)為 int數(shù)組并返回
- 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
題目描述 ：從上到下按層打印二叉樹，同一層的節(jié)點(diǎn)按從左到右的順序打印，每一層打印到一行。
“例如：給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回其層次遍歷結(jié)果：
- [
- [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
“題目描述： 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。例如: 給定二叉樹: [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回其層次遍歷結(jié)果：
- [
- [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()) {
- // 打印奇數(shù)層
- List<Integer> tmp = new ArrayList<>();
- for(int i = deque.size(); i > 0; i--) {
- // 從左向右打印
- TreeNode node = deque.removeFirst();
- tmp.add(node.val);
- // 先左后右加入下層節(jié)點(diǎn)
- if(node.left != null) deque.addLast(node.left);
- if(node.right != null) deque.addLast(node.right);
- }
- res.add(tmp);
- if(deque.isEmpty()) break; // 若為空則提前跳出
- // 打印偶數(shù)層
- tmp = new ArrayList<>();
- for(int i = deque.size(); i > 0; i--) {
- // 從右向左打印
- TreeNode node = deque.removeLast();
- tmp.add(node.val);
- // 先右后左加入下層節(jié)點(diǎn)
- 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
責(zé)任編輯：武曉燕
來源：
程序員千羽
