共计 1235 个字符,预计需要花费 4 分钟才能阅读完成。
题目描述
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
思路
该题和按照之字形打印二叉树差不多,需要每一层输出一行,也就是每一层需要输出一个 list, 那么需要两个队列进行合作,一个队列出队(保存上一层节点),一个队列入队(保存前一个队列的左右节点,即下一层节点),只不过该题和按照之字形二叉树打印的区别在于,之字形二叉树需要区分奇数层和偶数层,那么就需要两个队列保存左右节点的顺序不一样,上一个队列先保存左节点,再保存右节点;下一个队列先保存右节点,再保存左节点。
代码
import java.util.ArrayList;
import java.util.LinkedList;
public class Print1 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {this.val = val;}
}
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> list = new ArrayList<>();
if(pRoot == null) return list;
LinkedList<TreeNode> queue1 = new LinkedList<>();
LinkedList<TreeNode> queue2 = new LinkedList<>();
queue1.add(pRoot);
while (!queue1.isEmpty() || !queue2.isEmpty()){if(!queue1.isEmpty()){ArrayList<Integer> subList = new ArrayList<>();
while (!queue1.isEmpty()){TreeNode curNode = queue1.pollFirst();
subList.add(curNode.val);
if(curNode.left != null){queue2.add(curNode.left);
}
if(curNode.right != null){queue2.add(curNode.right);
}
}
list.add(subList);
}else {ArrayList<Integer> subList1 = new ArrayList<>();
while (!queue2.isEmpty()){TreeNode curNode = queue2.pollFirst();
subList1.add(curNode.val);
if(curNode.left != null){queue1.add(curNode.left);
}
if(curNode.right != null){queue1.add(curNode.right);
}
}
list.add(subList1);
}
}
return list;
}
}
正文完