当前位置：首页 > news >正文

【CT】LeetCode手撕—102. 二叉树的层序遍历

news 来源：原创 2024/9/28 23:07:23

题目

原题连接：102. 二叉树的层序遍历

1-思路

1.借助队列 Queue ，每次利用 ①while 循环遍历当前层结点，②将当前层结点的下层结点放入 Queue中
2.每遍历一个结点，将值收集到 iterm 中，每一层遍历完，将结果存到 res 中

2- 实现

⭐102. 二叉树的层序遍历——题解思路

在这里插入图片描述

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

3- ACM实现

3-1 二叉树构造

在这里插入图片描述

public static TreeNode build(Integer[] nums){// 借助 queue 来实现二叉树构造Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < nums.length){TreeNode node = queue.poll();if(nums[index]!=null && index<nums.length){node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (nums[index]!=null && index<nums.length){node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;
}

3-2 整体实现

public class levelTraversal {static class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int x){val = x;}}public static TreeNode build(Integer[] nums){// 借助 queue 来实现二叉树构造Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < nums.length){TreeNode node = queue.poll();if(nums[index]!=null && index<nums.length){node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (nums[index]!=null && index<nums.length){node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}static List<List<Integer>> res = new ArrayList<>();public static List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if(root==null){return res;}queue.offer(root);while(!queue.isEmpty()){int len = queue.size();List<Integer> iterm = new ArrayList<>();while(len>0){TreeNode node = queue.poll();iterm.add(node.val);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}len--;}res.add(new ArrayList(iterm));}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入二叉树构造数组");String input = sc.nextLine();input = input.replace("[","");input = input.replace("]","");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for(int i = 0 ; i <parts.length;i++){if(!parts[i].equals("null")){nums[i] = Integer.parseInt(parts[i]);}else{nums[i] = null;}}TreeNode root = build(nums);List<List<Integer>> forRes = levelOrder(root);for(List<Integer> i:forRes){System.out.println(i.toString());}}}