1.题目描述
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如:
给定二叉树: [3,9,20,null,null,15,7],
1 2 3 4 5 6
|
> 3 > / > 9 20 > / > 15 7 >
|
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
2.解题思路
同【剑指offer - 60】
BFS广度优先搜索的扩展题
迭代思想:
我们将树上顶点按照层次依次放入队列结构中,队列中元素满足 FIFO(先进先出)的原则。在 Java 中可以使用 Queue 接口中的 LinkedList实现。
第 0 层只包含根节点 root ,算法实现如下:
(1)初始化队列只包含一个节点 root 和层次编号 0 : level = 0。
(2)当队列非空的时候:
1) 在输出结果 levels 中插入一个空列表,开始当前层的算法。
2)计算当前层有多少个元素:等于队列的长度。
3)将这些元素从队列中弹出,并加入 levels 当前层的空列表中。
4)将他们的孩子节点作为下一层压入队列中。
5)进入下一层 level++。
递归思想:
最简单的解法就是递归,首先确认树非空,然后调用递归函数 helper(node, level),参数是当前节点和节点的层次。程序过程如下:
(1)输出列表称为 ans,当前最高层数就是列表的长度 len(ans)。比较访问节点所在的层次 level 和当前最高层次 len(ans) 的大小,如果前者更大就向 ans 添加一个空列表。
(2)将当前节点插入到对应层的列表 ans[level] 中。
(3)递归非空的孩子节点:helper(node.left , level + 1)。helper(node.right, level + 1)。
3.代码
方法1:迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
执行用时 :
3 ms, 在所有 Java 提交中击败了55.91%的用户
内存消耗 : 36.5 MB, 在所有 Java 提交中击败了44.59%的用户 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> lists = new ArrayList<>(); if(root == null) return lists; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ ArrayList<Integer> tmp = new ArrayList<>(); int count = queue.size(); for(int i = 0; i<count;i++){ TreeNode node = queue.poll(); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); tmp.add(node.val); } lists.add(tmp); } return lists; }
|
方法2:递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
执行用时 : 2 ms, 在所有 Java 提交中击败了92.32%的用户 内存消耗 : 37.1 MB, 在所有 Java 提交中击败了42.97%的用户 class { List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) { if(root == null) return ans; helper(root,0); return ans; }
private void helper(TreeNode root, int level) { if(ans.size() == level) ans.add(new ArrayList<>()); ans.get(level).add(root.val);
if(root.left != null) helper(root.left,level+1); if(root.right != null) helper(root.right,level+1); } }
|
4.提交结果
近期评论