🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻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;}
}

返回第一页。☝

☕物有本末，事有终始，知所先后。🍭

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓

附：完整从数组建立树的运行代码

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+1if (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+2if (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;}
}