JZ76 洗掉鏈表中重復的結點
題目
給定一個二叉樹，回傳該二叉樹的之字形層序遍歷，（第一層從左向右，下一層從右向左，一直這樣交替）
例如，給定的二叉樹是{1,2,3,#,#,4,5}
該二叉樹之字形層序遍歷的結果是
[
[1],
[3,2],
[4,5]
]
方法 非遞回層次遍歷
思路
演算法實作
按照層次遍歷按層列印二叉樹的方式，每層分開列印，然后對于每一層利用flag標記，
第一層為false，之后每到一層取反一次，如果該層的flag為true，則記錄的陣列整個反轉即可，
具體做法：
step 1：首先判斷二叉樹是否為空，空樹沒有列印結果，
step 2：建立輔助佇列，根節點首先進入佇列，不管層次怎么訪問，根節點一定是第一個，那它肯定排在隊伍的最前面，初始化flag變數，
step 3：每次進入一層，統計佇列中元素的個數，更改flag變數的值，因為每當訪問完一層，
下一層作為這一層的子節點，一定都加入佇列，而再下一層還沒有加入，因此此時佇列中的元素個數就是這一層的元素個數，
step 4：每次遍歷這一層這么多的節點數，將其依次從佇列中彈出，然后加入這一行的一維陣列中，如果它們有子節點，依次加入佇列排隊等待訪問，
step 5：訪問完這一層的元素后，根據flag變數決定將這個一維陣列直接加入二維陣列中還是反轉后再加入，然后再訪問下一層，
代碼
package mid.JZ77按之字形順序列印二叉樹;
import java.util.ArrayList;
import java.util.Collections;
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 {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
TreeNode head = pRoot;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//如果為空，直接回傳
if (head == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(head);
//記錄是否反轉
boolean flag = true;
while (!queue.isEmpty()) {
ArrayList<Integer> row = new ArrayList<>();
int n = queue.size();
flag = !flag;
for (int i = 0; i < n; i++) {
TreeNode p = queue.poll();
row.add(p.val);
if (p.left != null) {
queue.offer(p.left);
}
if (p.right != null) {
queue.offer(p.right);
}
}
//奇數行反轉，偶數行不反轉
if (flag) {
Collections.reverse(row);
}
res.add(row);
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541065.html
標籤：其他
上一篇：MyBatis配置決議