聽不少大佬建議過——力扣刷題要從樹開始 ！
因為可以建立起套路化的思路~ 另外就是鍛煉好遞回的思想
所以 我們從樹開始~
本專題采用 前面提到的 “兔系刷題法”
不求鉆研多種解法 只求快速見題型快速刷題！

另外 力扣評論區里看見的——

樹的題目寫不出來，多背幾個模版就行，

前中后序、廣度深度遍歷、路徑和、深度，直徑，這些全部背下來，

感覺很有道理！多背些多理解些套路嘛！

本專題整理了tag中包括廣度優先搜索的部分題型 都較為簡單 適合初學者嗷

刷的這幾道廣度優先搜索都是使用迭代的方式對樹進行一個遍歷
都用到了一個佇列對節點進行暫時存盤
然后再將其按照順序扔到結果串列中

關于這類題型
我認為可以使用一個模板
下面分享一下 也是我非常耐的一道題——劍指 Offer 32 - I 從上到下列印二叉樹（其實就是層序遍歷列印二叉樹） 一個medium難度的easy題（挺好想的嗷~而且想明白了 刷熟練了套路就大體掌握了）
熟悉了這道題之后 可以解決好多題哦~
廢話少說 快來解決這個層序遍歷列印二叉樹的題！！！

下面是兩道模板題

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

我們的模板 一定要理解透 刷熟練它！

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

從上到下列印出二叉樹的每個節點，同一層的節點按照從左到右的順序列印，

例如:
給定二叉樹: [3,9,20,null,null,15,7],

     3
	/ \
   9  20
   	 /  \
    15   7

回傳：

[3,9,20,15,7]

解題思路

• 特例處理
• 初始化結果串列 和 包含所有根節點的佇列
• 進行BFS回圈 在佇列 queue 為空時跳出
• • 隊首元素出隊并記為 node
  • 將 node.val添加到結果串列 tmp尾部
  • 向佇列 queue中添加子節點（當前遍歷到的 node節點的子節點）
• 將結果串列轉換為結果陣列來輸出

用個回圈就ok遼~

Java代碼

迭代法

class Solution {
    public int[] levelOrder(TreeNode root) {
        // 01 特例處理
        if (root == null){
            return new int[0];
        }
        // 02 初始化佇列 結果串列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//初始化佇列 用于按順序存放遍歷到的每層的節點
        List<Integer> res = new ArrayList<Integer>();//初始化存結果的串列（但是這不是）
        queue.add(root);//先把根節點加到佇列中————層序遍歷第一個列印的節點

        //03 廣度優先搜索
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();//1 節點出隊
            res.add(node.val);//將節點按順序加入結果串列中
            if (node.left != null) queue.add(node.left);//如果下一層還有節點的話 將其入隊
            if (node.right != null) queue.add(node.right);//下一層沒節點的話 說明已經沒有需要加入佇列的節點了~
        }

        // 04 把串列轉換成陣列
        // 可以使用jdk8的新特性 stream流
        // return list.stream().mapToInt(Integer::intValue).toArray();
        // 但是上面這個速度會慢一些！
        int[] ans = new int[res.size()];//這個陣列才符合輸出條件~
        for (int i = 0; i <= res.size() - 1; i ++){
            ans[i] = res.get(i);//獲取佇列中的值 要使用.get(i) 
        } 
        return ans;
    }
}

102.二叉樹的層序遍歷

和上一題差不多意思~

102. 二叉樹的層序遍歷

給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），

輸入：二叉樹：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

輸出：

[
  [3],
  [9,20],
  [15,7]
]

解題思路

在樹的遍歷中 使用了 BFS(Breadth-First-Search) 也就是廣度優先搜索演算法解決

【1】特例處理 判斷邊界條件——根為空

【2】初始化 創建 存放每層節點的佇列queue 結果串列res

Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList();

別忘了根節點入隊 queue.add(root);

【3】進行BFS廣度優先搜索

{1}新建一個臨時串列 用于存盤當前層的列印結果

List<Integer> temp = new ArrayList<>();

{2}進行回圈 把佇列中的節點值 node.val 按序添加到臨時串列temp的尾部 & 把加入串列節點的子節點加入到佇列中

			for(int i = 0; i < levelNum; i++){
                //3 把佇列中的元素加到臨時串列中 
                TreeNode node = queue.poll();//節點入隊
                temp.add(node.val);//加入當層結果中
     			// 4 結束每一個的元素的添加后 都要看一下它是否有下一層 
                // 如果有 就入到佇列中排隊去~
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
			//5 每層節點按序排好后加入到 結果二維陣列 中
			res.add(temp);

【4】回傳最終結果 二維陣列 res ~

Java代碼

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //01 判斷邊界條件
        if(root == null){
            return new ArrayList<>();
        }
        //02 佇列
        Queue<TreeNode> queue = new LinkedList<>();//存放每層的節點值
        List<List<Integer>> res = new ArrayList();//創建二維陣列 結果
        //根節點入隊
        queue.add(root);
        //03 進行BFS廣度優先搜索
        while(!queue.isEmpty()){
            int levelNum = queue.size();//1 記錄每層的節點數量
            List <Integer> temp = new ArrayList<>();//2 新建一個臨時串列 存每層節點值
            for(int i = 0; i < levelNum; i++){
                //3 把佇列中的元素加到臨時串列中 
                TreeNode node = queue.poll();//節點出隊
                temp.add(node.val);//加入當層結果中

                // 4 結束每一個的元素的添加后 都要看一下它是否有下一層 
                // 如果有 就入到佇列中排隊去~
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            //5 每層節點按序排好后加入到 結果二維陣列中
            res.add(temp);
        }
        // 04 BFS結束 輸出最終結果
        return res;
    }
}

來做一些其他題強化下

111.二叉樹的最小深度 easy

111. 二叉樹的最小深度

給定一個二叉樹，找出其最小深度，

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，

**說明：**葉子節點是指沒有子節點的節點，

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：2

示例 2：

輸入：root = [2,null,3,null,4,null,5,null,6]
輸出：5

解題思路

【1】非遞回 廣度優先搜索

進行層序遍歷 如果遍歷到一個節點的左右子樹同時為空 就回傳最小深度

【2】遞回

借鑒一位大佬的遞回小技巧

• 寫出結束條件
• 不要把樹復雜化，就當做樹是三個節點，根節點，左子節點，右子節點
• 只考慮當前做什么，不用考慮下次應該做什么
• 每次呼叫應該回傳什么

Java代碼

【1】非遞回

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int count = 0;//記錄深度
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            count += 1;
            for(int i = 0; i < size; i ++){
                //每一層的遍歷 尋找是否有子節點
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null){
                    return count;
                }
                if (node.left) {
                    queue.add(node.left);
                }
                if(node.right); {
                    queue.add(node.right);
                }
            }
        }
        return count;
    }
}

【2】遞回

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if (root.left == null && root.left == null) return 1;
        if (root.left!=null && root.right != null) return Math.min(minDepth(root.left), minDepth(root.right));
        if (root.left != null) return minDepth(root.left);//只考慮當前一層的狀態~
        if (root.right != null) return minDepth(root.right);
    }
}

116.填充每個節點的下一個右側節點指標 medium

116. 填充每個節點的下一個右側節點指標

廣度優先搜索

給定一個 完美二叉樹 ，其所有葉子節點都在同一層，每個父節點都有兩個子節點，二叉樹定義如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，

初始狀態下，所有 next 指標都被設定為 NULL，

示例

輸入：root = [1,2,3,4,5,6,7]
輸出：[1,#,2,3,#,4,5,6,7,#]
解釋：給定二叉樹如圖 A 所示，你的函式應該填充它的每個 next 指標，以指向其下一個右側節點，如圖 B 所示，序列化的輸出按層序遍歷排列，同一層節點由 next 指標連接，'#' 標志著每一層的結束，

解題思路

參考題解 BFS解決（最好的擊敗了100%的用戶）

要求把二叉樹中每行都串聯起來 那么最適合的就是BFS 也就是一行一行逐層進行的層序遍歷~

大佬給出了一幅圖 很清晰~

在劍指 Offer 32 - I. 從上到下列印二叉樹簡單廣度優先搜索演算法的基礎上 自然而然地引出了第一種方法

【1】使用佇列

用佇列將每一層串起來很簡單

逐層遍歷并進行串聯 pre.next = node 即可

然而題目進階要求是 —— 使用常數級的時間復雜度

【2】不使用佇列

Java代碼

【1】使用佇列

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int levelCount = queue.size();//每一層的節點數量
            Node pre = null;//前一個節點設定為空的
            for (int i = 0; i < levelCount; i ++){
                Node node = queue.poll();//將當前佇列隊頭 進行出隊 賦給node
                //如果pre不為空（為空的話代表node節點得到的值恰好是本層的第一個~）則讓pre指向這個節點
                if(pre != null){
                    pre.next = node;
                }
                pre = node;//將遍歷到的這個節點賦給pre 即 讓這個節點成為“前一個節點”
                //遍歷到的這個節點如果有子節點 就加入佇列~
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        return root;
    }
}

N的時間復雜度

因為我們把節點不停的入隊 然后再不停的出隊

題目進階要求 使用常數級的時間復雜度

【2】不使用佇列

class Solution{
    public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我們可以把它看做是每一層的鏈表
        Node cur = root;
        while (cur != null) {
            //遍歷當前層的時候，為了方便操作在下一
            //層前面添加一個啞結點（注意這里是訪問
            //當前層的節點，然后把下一層的節點串起來）
            Node dummy = new Node(0);
            //pre表示訪下一層節點的前一個節點
            Node pre = dummy;
            //然后開始遍歷當前層的鏈表
            while (cur != null) {
                if (cur.left != null) {
                    //如果當前節點的左子節點不為空，就讓pre節點
                    //的next指向他，也就是把它串起來
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理參照左子樹
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //繼續訪問這一行的下一個節點
                cur = cur.next;
            }
            //把下一層串聯成一個鏈表之后，讓他賦值給cur，
            //后續繼續回圈，直到cur為空為止
            cur = dummy.next;
        }
        return root;
    }
}

117.填充每個節點的下一個右側節點指標II medium

這題其實是個深度優先搜索
但是用層序遍歷（廣度）也可以做 就是空間復雜度不滿足進階要求（因為用了佇列）

117. 填充每個節點的下一個右側節點指標 II

給定一個二叉樹（與116的區別就是不是完美二叉樹 但是用廣度優先搜索做的話 代碼其實是一樣的 反正都遍歷一遍嘛~）

二叉樹定義如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，

初始狀態下，所有 next 指標都被設定為 NULL，

解題思路和上一個一樣哦

感覺和116也沒有太大區別

就是本題如果再使用方法一會比較浪費空間（因為并不是所有節點都滿足完美二叉樹 排列得這么滿）

具體的看上面116就可以

617.合并二叉樹 easy

617. 合并二叉樹

給定兩個二叉樹，想象當你將它們中的一個覆寫到另一個上時，兩個二叉樹的一些節點便會重疊，

你需要將他們合并為一個新的二叉樹，合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點，

示例 1:

輸入: 
Tree 1                     Tree 2                  
          1                         2                   
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7 輸出:            
合并后的樹:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7	    	

解題思路

迭代方法

需要額外的資料結構來存盤1 2號樹的節點

可以借助堆疊和佇列來完成

重點是廣度優先搜索的邏輯

遞回方法

相當于前序遍歷嗷

重點同樣是dfs的做法

遞回方法單獨寫出來一個遞回的dfs方法

其中遞回的條件是這個方法的重點 搞明白了 就很容易地寫出來了

代碼邏輯

迭代方法

重點是廣度優先搜索的邏輯 如下：

【1】

• 兩棵樹的左節點都不為null時 就放入佇列中（其實用一個就行了 但是我用了兩個，，有點蠢哈哈 但是比較直觀嘛~）

• 右節點同理

【2】

不斷地從佇列中取出節點把它們相加

【3】

• 如果1號樹的左節點為null 而2號樹的左節點不為null 將2號樹的左節點賦給1號樹
• 右節點同理

【4】

最后回傳root1

遞回方法

遞回的條件：

遞回函式名稱 dfs(TreeNode root1, TreeNode root2)

【1】終止條件：樹1的節點為null 或者樹2的節點為null

if(root1 == null || root2 == null){
	return root1 == null ? root2 : root1;
}

【2】遞回函式內把兩個數的節點相加后 賦給樹1的節點

root1.val += root2.val;

【3】遞回地執行兩棵樹的左節點 遞回執行兩棵樹的右節點

root1.left = dfs(root1.left, root2.left);
root2.right = dfs(root2.left, root2.right);

【4】最侄訓傳root1

Java代碼

迭代方法

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        //這里其實創建一個佇列就OK了~ 按順序存兩個樹的節點
        Queue<TreeNode> queue1 = new LinkedList<>();//存左面樹的節點
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.add(root1);
        queue2.add(root2);
        //只要兩個佇列不都為空 就還沒遍歷到最后
        while(!queue1.isEmpty() || !queue2.isEmpty()){
            //進行廣度優先搜索 一層一層地遍歷 并將節點添加到
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            //如果兩個節點都在佇列中
            node1.val += node2.val;
            //01 遍歷到左邊的子節點
            if (node1.left != null && node2.left != null) {
                //1、2號樹對應節點如果都不為空 就加入到佇列中 
                queue1.add(node1.left);
                queue2.add(node2.left);
            }
            else if (node1.left == null){
                //1號樹對應節點如果為空 把2號樹對應節點移過來
                node1.left = node2.left;
            }
            //02 右邊的子節點同理
            if (node1.right != null && node2.right != null) {
                queue1.add(node1.right);
                queue2.add(node2.right);
            }
            else if (node1.right == null){
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

遞回方法

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null){
            return root1 == null ? root2:root1;
        }
        return dfs(root1, root2);
    }    
    public TreeNode dfs(TreeNode r1, TreeNode r2){
        //遞回函式
       if(r1 == null || r2 == null){
           return r1 == null ? r2 : r1;
        }
        r1.val += r2.val;
        r1.left = dfs(r1.left,r2.left);
        r1.right = dfs(r1.right, r2.right);
        return r1;
    }
}