前言

剛開始寫演演算法題時，看到樹的題就要煩死了，現在比以前好了點，但也總是忘記思路（畢竟日常真的很少用到這些），開一個坑記錄一下樹相關的題解吧~

樹的層序遍歷

從最基本的二元樹開始，樹的層序遍歷通常來說就是按照樹的層數，從上往下的將每一層，按每一層從左到右的順序遍歷出來：

劍指 Offer 32 - I. 從上到下列印二元樹

像這樣的二元樹，通過層序遍歷遍歷出來的結果應該是[3,9,20,15,17]

在沒有任何其它特殊要求的情況下，我們藉助佇列直接把樹層序遍歷出來：

import java.util.*;
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        // 空值檢測        
        if(root == null){
            return new int[0];
        }
        // 藉助佇列在存放樹節點
        Queue<TreeNode> queue=new LinkedList<>();
        
        queue.offer(root);
        while(!queue.isEmpty()){
        	// 拿出隊頭進行操作
        	TreeNode tmp = queue.poll();
        	// 這裡的入隊操作是先左後右，保證每層的列印順序是從左到右
        	// 當隊頭的左節點非空，將其左節點入隊
            if(tmp.left != null){
                queue.offer(tmp.left);
            }
        	// 當隊頭的左節點非空，將其左節點入隊
            if(tmp.right != null){
                queue.offer(tmp.right);
            }
            // 將當前取出的隊頭輸出（新增到結果列表）
        	res.add(tmp.val);
        }
        // 將List轉化為int[]
    	return res.stream().mapToInt(Integer::valueOf).toArray();
	}
}

題解

學會了用佇列來做層序遍歷後，我們會遇到一些題目讓你應用層序遍歷來解題，如：

劍指 Offer 32 - II. 從上到下列印二元樹 II

力扣連結

和之前簡單的列印出一個陣列相比，這道題還需要對每一層的節點進行分割，加大了難度
我們可以在之前的基礎上改造一下，使層次遍歷的每一層都能在我們的掌握之中

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
        	// 每次進入while迴圈時，判斷【當前佇列】長度
            int len = queue.size();
            // 建立一個ArrayList物件
            // 用來新增當前層（即【當前佇列】）的節點值
            List<Integer> list = new ArrayList<>();
            // 遍歷【當前佇列】
            while(len-- > 0){
                TreeNode tmp = queue.poll(); 
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
                // 將【當前佇列】的值都裝進list中
                list.add(tmp.val);
            }
            // 將list裝入res列表中
            res.add(list);
        }
        return res;
    }

為什麼佇列的長度=每一層的節點個數呢？我們從第一層開始推：

• 當佇列中只有根節點時，佇列長度為1，通過獲取根節點的左右節點，並將根節點出隊，我們可以得到下一層的佇列中有根節點的左節點和右節點
• 此時佇列長度為2，對該佇列進行遍歷，獲取該佇列中的節點，並由這些節點獲取到這些節點的左/右子節點
• 在以後的外層while迴圈中，每一次外層while迴圈獲取到的佇列長度都是樹每一層的節點個數

LeetCode 107. 二元樹的層次遍歷 II

力扣連結

這道題就是將劍指 Offer 32 - II. 從上到下列印二元樹 II的輸出反過來而已，直接在它的基礎上在最後加上Collection.reverse(List list)即可

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            while(len-- > 0){
                TreeNode tmp=queue.poll();
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
                list.add(tmp.val);
            }
            res.add(list);
        }
        // 遍歷完反轉一下
        Collections.reverse(res);
        return res;
    }

劍指 Offer 32 - III. 從上到下之字形列印二元樹 III

力扣連結

請實現一個函數按照之字形順序列印二元樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推。

之字形列印的話，最簡單的方式，在劍指 Offer 32 - II. 從上到下列印二元樹 II的基礎上，只需要活用Collections.reverse(List list)這個方法即可

    public List<List<Integer>> levelOrder(TreeNode root) {        
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        // 定義變數reverse，由於是偶數行需要反轉，所以初值為false
        boolean reverse = false;
        
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while(len-- > 0){
                TreeNode tmp = queue.poll();                
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
                list.add(tmp.val);
            }
            // 當reverse為true時，將list反轉
            if(reverse){
                Collections.reverse(list);
            }
            // 將reverse取反
            reverse =! reverse;
            res.add(list);
        }
        return res;
    }

通過定義一個布林型別的變數reverse作為判斷是否執行反轉列表的操作，可以很輕鬆的列印出之字形樹