NC15 求二叉树的层序遍历

vlambda
2020-12-02

NC15 求二叉树的层序遍历

NC15 求二叉树的层序遍历考过的企业 - 小米

题目描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）例如：给定的二叉树是{3,9,20,#,#,15,7},该二叉树层序遍历的结果是 [ [3], [9,20], [15,7] ]

考察关键点

1.二叉树的层序遍历，用广度优先搜索（BFS），广度优先搜索使用队列来实现2.该题目的返回结果要求返回结果中包含层信息，思考如何在BFS中融合如层序信息

解题思路

如果不考虑层序信息，BFS可以很简单的使用一个队列实现，如下代码是按照层序打印遍历结果

public void levelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode top = queue.pop(); System.out.println(top.val); if (top.left != null) { queue.add(top.left); } if (top.right != null) { queue.add(top.right); } }}

上面代码简单BFS已经让我们获取到了层序的遍历结果，但是此处还不包含打印的节点在二叉树的哪一层的信息，那我们尝试修改上述代码来增加层数信息。这里我们尝试在这个while循环上做做文章，若每次while循环只处理同一层的节点，并在循环中把这一层所有节点的值放入一个列表中存入结果集，那么就可以求出题目要求的结果，那么现在这个问题就变成，如何保证一次while循环只处理二叉树一层的节点呢？这里我们再回到帮助我们进行BFS的队列，如果我们能保证每次开始一次while循环时，队列里只有同一层的数据，并且处理完这一层所有的数据后，再进入下一次循环，那么这个问题就解决了，OK，直接看代码。

 public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (root == null) { return ret; } // 用于BFS的队列 LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int len = queue.size(); // 初始化同一层的数组 ret.add(new ArrayList<>()); // 进入while循环时，队列中都是同一层的节点，并且在本次while循环中将这一层的所有节点处理完，所以这里取一开始进入循环时的队列长度，并取出同一层所有的节点放入结果集 for (int i = 0; i < len; i++) { TreeNode top = queue.pop(); // 放入这一层对应的数组中 ret.get(ret.size() - 1).add(first.val); System.out.println(top.val); // 将下一层的节点放入队列，准备进行下一次while循环 if (top.left != null) { queue.add(top.left); } if (top.right != null) { queue.add(top.right); } }
 } return ret; }

完整代码

package NC15;
import java.util.*;

class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

 public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}

public class NC15 { /** * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (root == null) { return ret; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int len = queue.size(); ret.add(new ArrayList<>()); for (int i = 0; i < len; i++) { TreeNode top = queue.pop(); ret.get(ret.size() - 1).add(first.val); System.out.println(top.val); if (top.left != null) { queue.add(top.left); } if (top.right != null) { queue.add(top.right); } }
 } return ret; }
 public static void main(String[] args) { TreeNode root = new TreeNode(3, new TreeNode(9, new TreeNode(15, null, null), new TreeNode(7, null, null)), new TreeNode(20, null, null)); System.out.println(levelOrder(root)); }
}