二叉树的层次遍历 Posted on 2021-06-10 00:00:00 2022-04-13 00:00:00 by Author 摘要 给定一颗二叉树，你能从左到右从上到下遍历这棵二叉树吗？？？？？？ # 二叉树的层次遍历 > 写于2021/06/10 1. 题目描述 - 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。 2. 示例描述 - 示例一 - 输入：  - 输出：[1, 2, 3] - 示例二 - 输入：  - 输出：[1, 2, 3, 6, 7, 8, 9] 3. 解题思路 - 二叉数的层次遍历就是对一颗二叉树从上到下从左到右，依次遍历一遍。这里我们拿示例二举个栗子，先访问第一层的节点`1`，然后访问第二层的节点`2`，在访问第三层的节点`3`和`6` ，最后在访问第四次层的节点`7`,`8`,`9`，这个过程中我们可以看出，访问的顺序是按照层次依次访问的，那么这个过程中，我们是否想到一种数据结构叫做队列尼，队列的特点就是先进先出，也就是先来到的节点先访问，后来的节点后处理。 - 对于这个层次遍历的算法，我们可以使用队列来解决，每一层的节点，先访问该节点，然后如果该节点有左右孩子，那么就把左右孩子加入到队列中，然后继续该层的下一个节点，该层所有节点都访问完了，同时他下一层的节点也按照顺序进入队列中了，那么该层按照层次遍历访问了，下一层也是按照本层一样的操作，直到访问到最底层，队列中元素为空，那么层次遍历整棵二叉树的操作也就结束了。具体代码如下所示，每一步都有详细的解释。 4. 代码示例 ```java public List<List<Integer>> levelOrder(TreeNode root) { //定义一个结果集 List<List<Integer>> result = new ArrayList<>(); //如果根节点为空，直接返回结果集 if(root == null){ return result; } //定义一个类型为二叉树节点的队列 Deque<TreeNode> deque = new ArrayDeque<>(); //定义一个二叉树临时节点，方便后面操作 TreeNode temp; //定义每一层开始的位置（从下标0开始计算，每个节点的位置） int start = 0; //根节点不为空，加入到队列中 deque.add(root); //这个mid变量是为了保存在每一层结束的位置 int mid = 1; //定义下一层结束的位置 int end = 1; while(!deque.isEmpty()){ //每一层都是一个List集合，所以定义一个结果集和的子集 List<Integer> re = new ArrayList<>(); //如果本层没有遍历完成,就继续遍历 while(start!=mid){ //先弹出队头元素 temp = deque.pop(); //继续下一节点，那么start要++ start++; //把结果加入到本层的子集和中 re.add(temp.val); //如果该节点有左孩子，那么左孩子进栈 if(temp.left!=null){ deque.add(temp.left); //同时下一层结束的位置要加1 end++; } //如果该节点有右孩子，那么右孩子进栈 if(temp.right!=null){ //同时下一层结束的位置要加1 deque.add(temp.right); end++; } //如果本层遍历完成了（及就是start和mid都到了下一层的开始位置），就结束本层的循环 //否则继续执行本层的操作 if(start == mid){ //同时mid改成下一层结束的位置 mid = end; //本层的结果集合加入到最终结果集合中 result.add(re); //跳出本层 break; } } } //返回最终结果 return result; } ``` 解法二 ```java public List<List<Integer>> levelOrder(TreeNode root) { //定义结果集合 List<List<Integer>> result = new ArrayList<>(); //如果为空树，直接返回 if (root == null) return result; //否则建立一个队列，把根节点加入队列中 Deque<TreeNode> deque = new ArrayDeque<>(); deque.add(root); while (!deque.isEmpty()) { //得到本次要遍历节点的个数 int size = deque.size(); List<Integer> temp = new ArrayList<>(); TreeNode point; //在遍历本层节点的时候，把下层节点加入队列中，同时队弹出本次节点，只保留下层节点 for (int i = 0; i < size; i++) { point = deque.pop(); temp.add(point.val); if (point.left != null) { deque.add(point.left); } if (point.right != null) { deque.add(point.right); } } //本层节点访问完毕，加入结果集合中 result.add(temp); } //返回最终结果 return result; } ```
{{ item.content }}
{{ child.content }}