文章目录
一、二叉树的分层遍历
直接遍历不现实，因为越往后结点越多，而且并不是每层结点都是2k-1。
如果遍历一个结点后，将该结点的孩子保存起来，下一次从结构中获取，这里保存孩子采用队列（先放入空间中的结点先被访问）来实现。
步骤：
1.先需要new一个队列—>将来队列中放置的元素就是结点的引用
2.先将root入队列
3.如果队列不为空，循环进行如下操作：获取队头元素—poll
遍历该结点
检测该结点如果有左孩子，让左孩子入队列
检测该结点如果有右孩子，让右孩子入队列
代码实现：
public void levelOrder(){
if(root==null){
return;
}
//二叉树不为空，需要借助队列完成二叉树的层序遍历
Queue<BTNode> q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
BTNode cur=q.poll(); //获取队头元素并出队列
System.out.print(cur.value+" ");
//如果cur的左孩子存在，则让cur的左孩子入队列
if(cur.left!=null){
q.offer(cur.left);
}
//如果cur的右孩子存在，则让cur的右孩子入队列
if(cur.right!=null){
q.offer(cur.right);
}
}
}
二、二叉树的层序遍历（LeetCode）
1.题目描述
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
2.输入输出示例
示例：
二叉树：[3,9,20,null,null,15,7],
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
3.思路分析
题目要求的返回值是二维数组，一个一维数组中放置一层的结点，这就意味着我们一次要保存一层的结点
一次保存一层，那么我们每次都要遍历队列中所有的元素，但是层数不同，队列里的元素个数就会不同，使用levelSize来记录元素个数
其他的都和上边自己实现的相同
4.代码实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> tree=new ArrayList<>();
if(root==null){
return tree;
}
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
//队列中保存的就是同一层节点
//一次性将该层的节点遍历完
int levelSize=q.size();
List<Integer> level=new ArrayList<>();
for(int i=0;i<levelSize;i++){
TreeNode cur=q.poll();
level.add(cur.val);
if(cur.left!=null){
q.offer(cur.left);
}
if(cur.right!=null){
q.offer(cur.right);
}
}
//上一层的节点已经遍历结束，队列中现在保存的刚好是下一层节点
tree.add(level);
}
return tree;
}
}
三、层序遍历Ⅱ（LeetCode）
1.题目描述
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
2.输入输出示例
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层序遍历为：
[
[15,7],
[9,20],
[3]
]
3.思路分析
本题在上面一题上做出的改变仅仅是逆序输出
我们不难想到栈是先入后出，所以这里我们可以先把原本要直接存入tree中的元素暂时存储到栈当中，等所有的结点存储完成后再从栈中倒到tree当中，就实现了逆置
4.代码实现
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> tree=new ArrayList<>();
if(root==null){
return tree;
}
Queue<TreeNode> q=new LinkedList<>();
Stack<List<Integer>> s=new Stack<>();
q.offer(root);
while(!q.isEmpty()){
//队列中保存的就是同一层节点
//一次性将该层的节点遍历完
int levelSize=q.size();
List<Integer> level=new ArrayList<>();
for(int i=0;i<levelSize;i++){
TreeNode cur=q.poll();
level.add(cur.val);
if(cur.left!=null){
q.offer(cur.left);
}
if(cur.right!=null){
q.offer(cur.right);
}
}
//上一层的节点已经遍历结束，队列中现在保存的刚好是下一层节点
//将每层的元素暂时存储到栈中
s.push(level);
}
//从栈中导入tree实现逆置
while(!s.empty()){
tree.add(s.pop());
}
return tree;
}
}