搞了这么久终于到了一道中等题。
描述给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0 le n le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)
例如：
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
其实没啥思路，就是有点想当然，在入栈队列改一下就好，其实思路完全错。
private void levelTravel(TreeNode root) {
//层序遍历和深度遍历不同，这个是广度优先遍历，我记得之前用迭代法更方便一些
//感觉用队列存放会方便一些，之字型的话，就是普通层序遍历加个特殊判断就好
Queue queue = new linkedList<>();
queue.add(root);//先把最开始的一个节点放入
int a = 1;//感觉要加一个变量用于记录是单数行还是双数行
int b = 1;//用来记录一行是都遍历完了，现在因为加入了一个节点所以为1
while (queue != null){//这个判断不为空但是不知道下一个循环的判断该是什么
ArrayList path = new ArrayList<>();
//题目是如果根节点为第一行的话，单数行正常放入，双数行翻转顺序放入
//因为是要遍历一行，所以要判断的应该是两个循环
int i = 0;
while (b != 0) {//我能想到的只有一种就是还是用int型数据标记一行的元素有几个，一旦减到0就退出循环
root = queue.poll();
if (a % 2 == 1) {//单数行
if (root.left != null) {
queue.add(root.left);
i++;
}
if (root.right != null){
queue.add(root.right);
i++;
}
b--;
} else {//双数行
if (root.right != null) {
queue.add(root.right);
i++;
}
if (root.left != null) {
queue.add(root.left);
i++;
}
b--;
}
path.add(root.val);
}
b = i;
res.add(path);
a++;
}
}
首先这堆代码有个很无语的错误在于，有个循环的条件判断写错了（大哥，队列不是链表）
while (queue != null){//就是这行
应该改为
while (queue.size() != 0){/
如果不改的话，这个就是个死循环出不来了，写size也好，isEmpty（）也好，反正别写我那种写法。错的让人无语。
实际上这个代码的逻辑错误在于，如果把双数行的代码放进去，下一行的顺序一定会乱，这就是我觉得很难处理的点，我现在的思路变成了，要不正常层序遍历一次，然后对结果的双数行再处理。要么就是在处理过程就写好，但是由于我这个是用队列实现的，它没办法打乱顺序输出在存入，所以我接下来的思路是用第一种方法正常层序遍历完再改变双数行的值。
//给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
ArrayList> res = new ArrayList<>();
public ArrayList> Print(TreeNode pRoot) {
if (pRoot == null)
return new ArrayList<>();
levelTravel(pRoot);
return res;
}
private void levelTravel(TreeNode root) {
//层序遍历和深度遍历不同，这个是广度优先遍历，我记得之前用迭代法更方便一些
//感觉用队列存放会方便一些，之字型的话，就是普通层序遍历加个特殊判断就好
Queue queue = new linkedList<>();
queue.add(root);//先把最开始的一个节点放入
int a = 1;//感觉要加一个变量用于记录是单数行还是双数行
int b = 1;//用来记录一行是都遍历完了，现在因为加入了一个节点所以为1
while (queue.size() != 0){//这个判断不为空但是不知道下一个循环的判断该是什么
ArrayList path = new ArrayList<>();
//题目是如果根节点为第一行的话，单数行正常放入，双数行翻转顺序放入
//因为是要遍历一行，所以要判断的应该是两个循环
int i = 0;
while (b != 0) {//我能想到的只有一种就是还是用int型数据标记一行的元素有几个，一旦减到0就退出循环
root = queue.poll();
if (root.left != null) {
queue.add(root.left);
i++;
}
if (root.right != null){
queue.add(root.right);
i++;
}
path.add(root.val);
b--;
}
b = i;
if (a % 2 == 1)
res.add(path);
else{
ArrayList arrayList = new ArrayList();
for (int j = path.size() - 1; j >= 0 ; j--) {
arrayList.add(path.get(j));
}
res.add(arrayList);
}
a++;
}
}
哈哈哈哈，发现不能用reverse就用了个蠢办法了，看看别人的代码。
import java.util.linkedList;
public class Solution {
public ArrayList > Print(TreeNode pRoot) {
linkedList q = new linkedList<>();
ArrayList> res = new ArrayList<>();
boolean rev = true;
q.add(pRoot);
while(!q.isEmpty()){
int size = q.size();
ArrayList list = new ArrayList<>();
for(int i=0; i
很简洁了，不会调用那么多乱七八糟的变量，学习学习。
顺便放一下生成二叉树的测试用例
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static TreeNode constructTree(Integer[] nums){
if (nums.length == 0) return new TreeNode(0);
Deque nodeQueue = new linkedList<>();
// 创建一个根节点
TreeNode root = new TreeNode(nums[0]);
nodeQueue.offer(root);
TreeNode cur;
// 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2）
int lineNodeNum = 2;
// 记录当前行中数字在数组中的开始位置
int startIndex = 1;
// 记录数组中剩余的元素的数量
int restLength = nums.length - 1;
while(restLength > 0) {
// 只有最后一行可以不满，其余行必须是满的
// // 若输入的数组的数量是错误的，直接跳出程序
// if (restLength < lineNodeNum) {
// System.out.println("Wrong Input!");
// return new TreeNode(0);
// }
for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) {
// 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
if (i == nums.length) return root;
cur = nodeQueue.poll();
if (nums[i] != null) {
cur.left = new TreeNode(nums[i]);
nodeQueue.offer(cur.left);
}
// 同上，说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
if (i + 1 == nums.length) return root;
if (nums[i + 1] != null) {
cur.right = new TreeNode(nums[i + 1]);
nodeQueue.offer(cur.right);
}
}
startIndex += lineNodeNum;
restLength -= lineNodeNum;
lineNodeNum = nodeQueue.size() * 2;
}
return root;
}
public static void preOrder(TreeNode root) {//前序排列
if (root == null) return;
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
public static void midOrder(TreeNode root) {//中序排列
if (root == null) return;
midOrder(root.left);
System.out.print(root.val + " ");
midOrder(root.right);
}
public static void aftOrder(TreeNode root) {//后序排列
if (root == null) return;
aftOrder(root.left);
aftOrder(root.right);
System.out.print(root.val + " ");
}
public static void main(String[] args) {
Integer[] nums = {1,2,3,4,5,6,7};
TreeNode tree=constructTree(nums);
TreeTest treeTest = new TreeTest();
System.out.println(treeTest.Print(tree));
}
