題目
給定一個二叉樹，回傳其節點值的鋸齒形層序遍歷，（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行），
示例
給定二叉樹 [3,9,20,null,null,15,7],
回傳鋸齒形層序遍歷如下：
[
[3],
[20,9],
[15,7]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
Java代碼實作
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) { //二叉樹為空，直接回傳空結果
return res;
}
ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();
deque.add(root);
leverOrder(res, deque, 1);
return res;
}
/*
* 引數串列說明：
* res 結果集
* deque 雙向佇列存盤當前層次遍歷的結點
* flag 記錄當前遍歷的層數，用來控制層序遍歷的方向
*/
void leverOrder(List<List<Integer>> res,ArrayDeque<TreeNode> deque,int flag) {
int size = deque.size();
if(size == 0) {
return;
}
ArrayList<Integer> arrayList = new ArrayList<Integer>();
if(flag == 1) {
while(size-- != 0) {
TreeNode root = deque.pollFirst();
arrayList.add(root.val);
if(root.left != null) {
deque.offer(root.left);
}
if(root.right != null) {
deque.offer(root.right);
}
}
//加入結果集，遞回下一層
res.add(arrayList);
leverOrder(res, deque, 2);
}else {
while(size-- != 0) {
TreeNode root = deque.pollLast();
arrayList.add(root.val);
if(root.right != null) {
deque.offerFirst(root.right);
}
if(root.left != null) {
deque.offerFirst(root.left);
}
}
//加入結果集，//遞回下一層
res.add(arrayList);
leverOrder(res, deque, 1);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239942.html
標籤：其他