【CT】LeetCode手撕—103. 二叉树的锯齿形层序遍历

---

题目

• 原题连接：103. 二叉树的锯齿形层序遍历

---

1- 思路

• 二叉树的层序遍历，遇到奇数时，利用 Collections.reverse() 翻转即可

---

2- 实现

⭐103. 二叉树的锯齿形层序遍历——题解思路

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> zigzagLevelOrder(TreeNode root) {return Traversal(root);}public List<List<Integer>> Traversal(TreeNode root){if(root==null){return res;}// 借助 queueQueue<TreeNode> queue = new LinkedList<>();queue.offer(root);// queue 不空int count = 0;while(!queue.isEmpty()){int len = queue.size();List<Integer> path = new ArrayList<>();while(len>0){TreeNode node = queue.poll();path.add(node.val);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}len--;}count++;if(count%2==1){res.add(new ArrayList(path));}else{Collections.reverse(path);res.add(new ArrayList(path));}}return res;}
}

---

2- ACM实现

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<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>> levelTraversal(TreeNode root){if(root==null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int level = 0;while(!queue.isEmpty()){List<Integer> iterm = new ArrayList<>();int len = queue.size();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--;}if(level%2==1) {Collections.reverse(iterm);}res.add(new ArrayList<>(iterm));}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);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);levelTraversal(root);System.out.println("结果为"+res.toString());}
}