[[438363]]

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

“題目描述 ：從上到下打印出二叉樹的每個節(jié)點，同一層的節(jié)點按照從左到右的順序打印。例如：給定二叉樹: [3,9,20,null,null,15,7],

     3 
    / \ 
  9  20 
 /  \ 
15   7 

返回：

[3,9,20,15,7] 

提示：節(jié)點總數(shù) <= 1000

解題思路：

• 題目要求的二叉樹的 從上至下 打印(即按層打印)，又稱為二叉樹的 廣度優(yōu)先搜索(BFS)。
• BFS 通常借助 隊列 的先入先出特性來實現(xiàn)。

算法流程：

• 特例處理： 當樹的根節(jié)點為空，則直接返回空列表 [] ;
• 初始化： 打印結(jié)果列表 res = [] ，包含根節(jié)點的隊列 queue = [root] ;
• BFS 循環(huán)： 當隊列 queue 為空時跳出;
  • 出隊： 隊首元素出隊，記為 node;
  • 打?。?將 node.val 添加至列表 tmp 尾部;
  • 添加子節(jié)點： 若 node 的左(右)子節(jié)點不為空，則將左(右)子節(jié)點加入隊列 queue ;
• 返回值： 返回打印結(jié)果列表 res 即可。

復雜度分析：

1. 時間復雜度 O(N)： N為二叉樹的節(jié)點數(shù)量，即 BFS 需循環(huán) N次。
2. 空間復雜度 O(N) ：最差情況下，即當樹為平衡二叉樹時，最多有 N/2 個樹節(jié)點同時在 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 
 * @微信公眾號 程序員千羽 
 * @個人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 從上到下打印二叉樹 思路：利用隊列（鏈表）輔助實現(xiàn)。 
 * 
 * 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];//空樹則返回空數(shù)組 
        ArrayList<Integer> list = new ArrayList<>();// 申請一個動態(tài)數(shù)組 ArrayList 動態(tài)添加節(jié)點值 
        Queue<TreeNode> queue = new LinkedList<>(); 
        queue.offer(root);// 根結(jié)點先入隊 
        while (!queue.isEmpty()) { 
            TreeNode node = queue.poll();// 取出當前隊首元素 
            list.add(node.val); 
            if (node.left != null) queue.offer(node.left);// 左子節(jié)點入隊 
            if (node.right != null) queue.offer(node.right);// 右子節(jié)點入隊 
        } 
        // 將 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é)點按從左到右的順序打印，每一層打印到一行。

“例如：給定二叉樹: [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

“題目描述： 請實現(xiàn)一個函數(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é)點 
                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é)點 
                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