1,BFS解决
其实这就是二叉树的BFS,也可以看下之前讲的373,数据结构-6,树 ,
就是这样,一层一层打印,使用队列解决
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { //边界条件判断 if (root == null) return new ArrayList<>(); //队列 Queue<TreeNode> queue = new LinkedList<>(); ArrayList<ArrayList<Integer>> res = new ArrayList<>(); //根节点入队 queue.add(root); //如果队列不为空就继续循环 while (!queue.isEmpty()) { //BFS打印,levelNum表示的是每层的结点数 int levelNum = queue.size(); //subList存储的是每层的结点值 ArrayList<Integer> subList = new ArrayList<>(); for (int i = 0; i < levelNum; i++) { //出队 TreeNode node = queue.poll(); subList.add(node.val); //左右子节点如果不为空就加入到队列中 if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } //把每层的结点值存储在res中, res.add(subList); } return res; }
2,DFS解决
这题让一层一层的打印,其实就是BFS,但使用DFS也是可以解决的,看一下
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); levelHelper(res, root, 0); return res; } public void levelHelper(ArrayList<ArrayList<Integer>> list, TreeNode root, int level) { //边界条件判断 if (root == null) return; //level表示的是层数,如果level >= list.size(),说明到下一层了,所以 //要先把下一层的list初始化,防止下面add的时候出现空指针异常 if (level >= list.size()) { list.add(new ArrayList<>()); } //level表示的是第几层,这里访问到第几层,我们就把数据加入到第几层 list.get(level).add(root.val); //当前节点访问完之后,再使用递归的方式分别访问当前节点的左右子节点 levelHelper(list, root.left, level + 1); levelHelper(list, root.right, level + 1); }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666