题目

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如: 给定二叉树: [3,9,20,null,null,15,7],

 3 / \ 9 20 / \ 15 7

返回其层次遍历结果：

[ [3], [9,20], [15,7] ]

题解

我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是： 如何确定是在同一层的。我们很自然的想到：如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。由于队列是先进先出的数据结构,所以这个列表是从左到右的。

/** * 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) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // 当前队列的大小就是上一层的节点个数, 依次出队 while (size > 0) { TreeNode current = queue.poll(); if (current == null) { continue; } currentRes.add(current.val); // 左子树和右子树入队. if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size--; } res.add(currentRes); } return res; } }

这道题可不可以用非递归来解呢?

递归的子问题：遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层

递归结束条件: 当前层,当前子树节点是 null

/** * 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) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } levelOrderHelper(res, root, 0); return res; } /** * @param depth 二叉树的深度 */ private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) { if (root == null) { return; } if (res.size() <= depth) { // 当前层的第一个节点,需要 new 一个 list 来存当前层. res.add(new LinkedList<>()); } // depth 层,把当前节点加入 res.get(depth).add(root.val); // 递归的遍历下一层. levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); } }