二叉树层次遍历，每行输出一层结果

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

示例：
二叉树：[1，2，3，4，5，NULL，7],

返回其层次遍历结果：

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

每天记录一下，保证彻底掌握。

分析：

	1.首先想要层次遍历，得清楚当前是哪一层，假如要输出第三层【4，5，7】，你得拿到【2，3】2.访问【2】节点，搞一个容器装【2】节点的子节点，再访问【3】节点，容器再加入【3】的子节点3.那么现在呢，这个容器就装好了第三层的结果

这只是一层的分析，有一个初步的思路。

然后再往下思考，想访问到【2】【3】节点，发现【2，3】节点刚好是第二层的结果

现在应该有思路了

递归是不是，遍历访问每一层的结果的子节点，就能得到下一层的结果。

这里我不使用递归，维护一个队列去保存每次要遍历节点

Queue<TreeNode> queue = new LinkedList<>();

现在开始写代码（写之前先考虑边界，空值，这里先省略），

1. 把根节点加入

queue.add(root);

2. 将根节点加入，当queue不为空【】，就对queue每个节点去进行上面分析的操作

为了实现让一层节点加入到同一集合，让这些节点处于同一个条件下进行add，即可加入到同一集合

int count= queue.size();
List<Integer> list = new ArrayList<>();
while(count>0){TreeNode node = queue.poll();list.add(node.val);if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}count--;
}

3. 将list加入到结果集

完整代码：

public class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return new ArrayList<>();}List<List<Integer>> res = new ArrayList<List<Integer>>();Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int count = queue.size();while (count > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}count--;}res.add(list);}return res;}
}
class TreeNode {TreeNode right;TreeNode left;int val;public TreeNode(int x) {val = x;}
}

再记录一个递归解法，有时候面试官会问有没有其他处理方式。

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return new ArrayList<>();}rec(root, 0);return res;}public void rec(TreeNode node, int level) {if (res.size() == level) {res.add(new ArrayList<>());}res.get(level).add(node.val);if (node.left != null) {rec(node.left, level + 1);}if (node.right != null) {rec(node.right, level + 1);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！