目录
题目概述(中等难度)
思路与代码
思路展现
方法1 层序遍历 + 双端队列
代码示例
方法2 层序遍历 + 倒序
代码示例
题目概述(中等难度)
题目链接:
点我进入链接
思路与代码
思路展现
方法1 层序遍历 + 双端队列
这块直接看K神题解就好,链接放到这里了:
戳我戳我
个人认为双端队列是需要掌握的,而且有了前面两道题目的铺垫,建议这道题目直接看代码就能理解K神的意思了.
代码示例
/** * 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) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root != null){ queue.add(root); } while(!queue.isEmpty()) { //定义一个双端队列 LinkedList<Integer> list = new LinkedList<>(); //注意这块的循环必须这样写 for(int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); if(res.size() % 2 == 0) { //偶数层,使用addLast方法放到队列头部 list.addLast(node.val); }else { //奇数层,使用addFirst方法放到队列尾部 list.addFirst(node.val); } if(node.left != null) { queue.add(node.left); } if(node.right != null) { queue.add(node.right); } } res.add(list); } return res; } }
方法2 层序遍历 + 倒序
这个方法跟我当时自己想的一样,奈何我根本不知道集合中的元素竟然还有反转方法,的确是骚.使用Collections.reverse()
方法即可。
代码示例
/** * 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) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root != null){ queue.add(root); } while(!queue.isEmpty()) { List<Integer> list = new ArrayList<>(); //注意这块的循环必须这样写 for(int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); list.add(node.val); if(node.left != null) { queue.add(node.left); } if(node.right != null) { queue.add(node.right); } } if(res.size() % 2 == 1) { //奇数层直接使用reverse方法反转 Collections.reverse(list); } res.add(list); } return res; } }