每天一道leetcode-102二叉树的层次遍历

• 2019 年 10 月 4 日
• 筆記

昨天的题解

题目

题目详解

思路

• 层次遍历肯定想到队列啊，通过判断队列是否为空，来判断是否遍历完整颗树
• 第一层到第二层的话，如何判断进入了下一层？这里利用一个临时变量teBePrinted,比如第一层肯定只有根节点这一个节点啊，那么初始toBEpRrinted = 1 然后每当队列出去一个节点，teBePrinted就减一，当teBePrinted为0的时候就进入到下一层了；
• 再次进入下一层，肯定有人要问，那么下一层的teBePrinted的这个值如何计算呢？这个就是每当上一层的节点出队，比如根节点出队root出队了，然后只要还没进入到下一层，那么就去判断这个出队节点root的左右节点left和right是不是等于null，只要不为null那么我们就记录一下这个不为null的节点数目，这样就把下一层的节点数目记录下来了！

代码

/**   * Definition for a binary tree node.   * public class TreeNode {   *     int val;   *     TreeNode left;   *     TreeNode right;   *     TreeNode(int x) { val = x; }   * }   */  class Solution {      public List<List<Integer>> levelOrder(TreeNode root) {          List<List<Integer>> list = new ArrayList<>();          List<Integer> tempList = new ArrayList<>();          if(root == null)              return list;          Queue<TreeNode> queue = new LinkedList<>();          queue.add(root);          int toBePrint = 1;//这一层要打印的节点          int nextLevelCount = 0;//下一层需要打印节点          while(queue.isEmpty() == false)//队列不为空          {              TreeNode temp = queue.poll();//出队              tempList.add(temp.val);//把需要的val保存下来              toBePrint--;//每出队一个，这层要打印的节点数就减少一个              if(temp.left != null)              {                  queue.add(temp.left);//入队，先入先出，所以左子树先打印                  nextLevelCount++;//统计下一层节点              }              if(temp.right != null)              {                  queue.add(temp.right);//和上面类似                  nextLevelCount++;              }              if(toBePrint == 0)//当这一层节点打印完了              {                  list.add(new ArrayList<>(tempList));//把这一行的结果保存                  tempList.clear();                  toBePrint = nextLevelCount;//下一层打印的节点，进行赋值                  nextLevelCount = 0;//下下层节点初始值置位0，准备开始计数              }          }          return list;      }  }

代码截图（避免乱码）