题目

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

例如:
给定二叉树: [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);}
}

热门阅读

• 技术文章汇总
• 【Leetcode】101. 对称二叉树
• 【Leetcode】100. 相同的树
• 【Leetcode】98. 验证二叉搜索树