牛客题霸NC14java版答案
二叉树的之字形层序遍历
https://www.nowcoder.com/practice/47e1687126fa461e8a3aff8632aa5559?tpId=117&&tqId=34935&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
题目描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树之字形层序遍历的结果是
[
[3],
[20,9],
[15,7]
]
题解
本题具体代码如下：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
boolean flag = false; //用于判断是否需要反转
while(!queue.isEmpty()){
ArrayList<Integer> tem = new ArrayList();
int size = queue.size(); //当前队列中元素得个数
for(int i = 0; i < size; i++){
TreeNode cur = queue.poll();
tem.add(cur.val);
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
}
if(!flag){
res.add(tem);
flag = !flag;
}
else{
Collections.reverse(tem);
res.add(tem);
flag = !flag;
}
}
return res;
}
} 二叉树层序遍历 import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> tem = new ArrayList();
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode cur = queue.poll();
tem.add(cur.val);
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
}
res.add(tem);
}
return res;
}
} 代码解释：
本题属于二叉树层序遍历得变形，利用队列暂存每一层得元素，将每一层遍历得结果存入结果中，由于是之字形遍历，所以用flag作为一个标记，用于判断是否需要反转。
查看20道真题和解析
，接着当手孝子