🍎道阻且长，行则将至。🍓
🌻算法，不如说它是一种思考方式🍀
算法专栏： 👉🏻123
可以参考👉LeetCode：二叉树的前、中、后序遍历——如何创建一棵【二叉树】
一、🌱102. 二叉树的层序遍历
- 题目描述：给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 - 来源：力扣（LeetCode）
- 难度：中等
- 提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
- 示例
🌴解题
1.递归法
也就是使用先序遍历，根据对每一层的深度来考虑增加集合元素，原理是很简单的，判断好递归何时结束即可。
- code：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
int deepth=1;
List<List<Integer>> ans=new ArrayList<>();//保存输出结果的集合
if(root==null)
return ans;
List<Integer> list=new ArrayList<>();//每一层的临时集合
visit(root,list,ans,deepth);//开始遍历
return ans;
}
private static void visit(TreeNode node, List<Integer> list,List<List<Integer>> ans, int deepth) {
if(node!=null) {//当前节点，以及是否可以继续下行
if (ans.size() >= deepth)
ans.get(deepth-1).add(node.val);
else {
list.add(node.val);
ans.add(new ArrayList<>(list));
list.clear();
}
//左右子树进递归
visit(node.left, list,ans, deepth + 1);
visit(node.right, list, ans, deepth + 1);
}
}
}
2.迭代法
使用一个队列来进行节点进队，仍然是先序遍历。这里使用到两个集合（一个最后的结果，一个是每一层的）和一个队列的数据结构。
可以用语言描述：
1、根节点入队;
2、然后在循环中是每次 判断 队列是否有节点（没有节点了代表遍历结束了）while;
2.1、计算出队长为 n；
2.2、对队列进行n次出队 for：
a、取出队的元素—— node；
b、每一层的集合—— add（node值）；
c、如果node有左右子节点：
左右节点 顺序进队；
2.3、结果的集合—— add（层集合值）；
结束
- code：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null) {
return resultList;
}
queue.offer(root);
while(!queue.isEmpty()) {
int currentLevelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for(int i = 0; i < currentLevelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
resultList.add(currentLevel);
}
return resultList;
}
}
东风夜放花千树，更吹落、星如雨。—— 辛弃疾
☕物有本末，事有终始，知所先后。🍭
附：完整从数组建立树的运行代码
package code;
import java.util.ArrayList;
import java.util.List;
public class c102 {
public static void main(String[] args) {
char[] root1 = {3,9,20,5,' ',15,7};
TreeNode102 root = new TreeNode102();
creatNode(root, root1, 0);
List list = Solution102.levelOrder(root);
for (Object o : list) {
System.out.print(o);
}
}
public static void creatNode (TreeNode102 p,char[] root1, int i){
if (i >= root1.length)
return;
p.setVal(root1[i]);//父节点
if (i * 2 + 1 < root1.length) {
//左子树 *2+1
if (root1[i * 2 + 1] != ' ') {
p.left = new TreeNode102();
creatNode(p.left, root1, i * 2 + 1);
} else p.left = null;
}
if (i * 2 + 2 < root1.length) {
//右子树 *2+2
if (root1[i * 2 + 2] != ' ') {
p.right = new TreeNode102();
creatNode(p.right, root1, i * 2 + 2);
} else p.right = null;
}
}
}
/**
* 层序遍历
*/
class Solution102 {
public static List<List<Integer>> levelOrder(TreeNode102 root) {
int deepth=1;
List<List<Integer>> ans=new ArrayList<>();
if(root==null)
return ans;
List<Integer> list=new ArrayList<>();
visit(root,list,ans,deepth);
return ans;
}
private static void visit(TreeNode102 node, List<Integer> list,List<List<Integer>> ans, int deepth) {
if(node!=null) {
if (ans.size() >= deepth)
ans.get(deepth-1).add(node.val);
else {
list.add(node.val);
ans.add(new ArrayList<>(list));
list.clear();
}
visit(node.left, list,ans, deepth + 1);
visit(node.right, list, ans, deepth + 1);
}
}
}
class TreeNode102 {
int val;
code.TreeNode102 left;
code.TreeNode102 right;
TreeNode102() {
}
TreeNode102(int val) {
this.val = val;
}
TreeNode102(int val, code.TreeNode102 right, code.TreeNode102 left) {
this.val = val;
this.left = left;
this.right = right;
}
public void setVal(int val) {
this.val = val;
}
public void setLeft(code.TreeNode102 left) {
this.left = left;
}
public void setRight(code.TreeNode102 right) {
this.right = right;
}
}
