JZ78 把二叉樹列印成多行
題目
給定一個節點數為 n 二叉樹，要求從上到下按層列印二叉樹的 val 值，同一層結點從左至右輸出，每一層輸出一行，
將輸出的結果存放到一個二維陣列中回傳，
例如：給定的二叉樹是{1,2,3,#,#,4,5}
[
[1],
[2,3],
[4,5]
]
方法 非遞回層次遍歷
思路
演算法實作
按照層次遍歷按層列印二叉樹的方式，每層分開列印，記錄陣列，
具體做法：
step 1：如果樹為空，則回傳空陣列，沒有任何列印結果，
step 2：使用佇列輔助層次遍歷，優先加入二叉樹的根節點，
step 3：從根節點開始，每次進入一層的時候，記錄佇列的長度即本層的節點數，
然后訪問相應節點數全在同一個陣列中，子節點加入佇列中繼續排隊，
step 4：每次訪問完一層將陣列加入二維陣列中再進入下一層，
代碼
package mid.JZ78把二叉樹列印成多行;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
//存放結果
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//如果根節點為null 直接回傳
if (pRoot == null) return res;
//定義佇列進行廣度遍歷
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
while (!queue.isEmpty()) {
//記錄每一層有幾個節點
int size = queue.size();
//記錄每一層的資料
ArrayList<Integer> row = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
//左子樹有值，入隊
queue.offer(node.left);
}
if (node.right != null) {
//右子樹有值，入隊
queue.offer(node.right);
}
//將值添加到層集合中
row.add(node.val);
}
res.add(row);
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541093.html
標籤：其他
上一篇：密碼加密，天經地義
下一篇：JavaSE：基礎語法