- 前言
- 一、N叉树层次遍历
- 二、分层遍历
- 1、递归遍历 + level分层
- 2、层次遍历+size分层
- 总结
- 参考文献
层次遍历是二叉树的基本遍历,分层遍历又是二叉树层次遍历的扩展。二叉遍历和N叉遍历不过是孩子节点由2到N。通过N叉树分层遍历来练习分层的两者思想,层次遍历+size分层 || 递归遍历+level分层。
一、N叉树层次遍历 二、分层遍历 1、递归遍历 + level分层// N叉树的层序遍历。
public class LevelOrder {
// M1-递归遍历 + level标记
public List> levelOrder(Node root) {
// 初始化需要的List来存各层list
List> rs = new ArrayList<>();
// 前序遍历 + 分层,使每个节点进入对应的list。
preOrder(root, rs, 0);
// 返回分层遍历的节点集。
return rs;
}
// 前序遍历 + level 做到分层取值。
private void preOrder(Node root, List> rs, int level) {
// 递归到null节点,终止此次递归。
if (null == root) return;
// 获取该root节点所在的list,并把该节点加入。
List cur = null;
// 第一次到这么深。
if (level >= rs.size()) rs.add(cur = new ArrayList<>());
else cur = rs.get(level);
// 将该节点放入对应层。
cur.add(root.val);
// 递归遍历。
List next = root.children;
for (Node node : next) preOrder(node, rs, level + 1);
}
// Definition for a Node.
class Node {
public int val;
public List children;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, List _children) {
val = _val;
children = _children;
}
}
}
2、层次遍历+size分层
// N叉树的层序遍历。
public class LevelOrder {
// M1-递归遍历 + level标记
public List> levelOrder(Node root) {
// 初始化需要的List来存各层list
List> rs = new ArrayList<>();
// 前序遍历 + 分层,使每个节点进入对应的list。
preOrder(root, rs, 0);
// 返回分层遍历的节点集。
return rs;
}
// 前序遍历 + level 做到分层取值。
private void preOrder(Node root, List> rs, int level) {
// 递归到null节点,终止此次递归。
if (null == root) return;
// 获取该root节点所在的list,并把该节点加入。
List cur = null;
// 第一次到这么深。
if (level >= rs.size()) rs.add(cur = new ArrayList<>());
else cur = rs.get(level);
// 将该节点放入对应层。
cur.add(root.val);
// 递归遍历。
List next = root.children;
for (Node node : next) preOrder(node, rs, level + 1);
}
// Definition for a Node.
class Node {
public int val;
public List children;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, List _children) {
val = _val;
children = _children;
}
}
}
总结
1)树分层遍历的两者思想,层次遍历+size分层 || 递归遍历+level分层。
参考文献[1] LeetCode N叉树层序遍历


![N叉树层序遍历[层次遍历+size分层 || 递归遍历+level分层] N叉树层序遍历[层次遍历+size分层 || 递归遍历+level分层]](http://www.mshxw.com/aiimages/31/948278.png)
