103.二叉树的锯齿形层序遍历

linwt · linwt · commit dd2722d01274 · 2022-04-05T14:26:13.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -33,6 +33,7 @@
 94. 二叉树的中序遍历
 101. 对称二叉树
 102. 二叉树的层序遍历
+103. 二叉树的锯齿形层序遍历
 104. 二叉树的最大深度
 105. 从前序与中序遍历序列构造二叉树
 114. 二叉树展开为链表
diff --git a/leetcode_Java/Solution0102.java b/leetcode_Java/Solution0102.java
@@ -31,12 +31,11 @@ public List<List<Integer>> levelOrder(TreeNode root) {
         if (root == null) {
             return list;
         }
-        List<Integer> sonList = new ArrayList<>();
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
-        int count;
         while (!queue.isEmpty()) {
-            count = queue.size();
+            int count = queue.size();
+            List<Integer> sonList = new ArrayList<>();
             while (count > 0) {
                 root = queue.remove();
                 sonList.add(root.val);
@@ -49,7 +48,6 @@ public List<List<Integer>> levelOrder(TreeNode root) {
                 count--;
             }
             list.add(sonList);
-            sonList = new ArrayList<>();
         }
         return list;
     }
@@ -106,7 +104,7 @@ public List<List<Integer>> levelOrder(TreeNode root) {
 *               局部变量：子列表存放每层节点值
 * 2、辅助标记：整型变量标记 层的深度 对应 子列表的索引
 * 3、递归逻辑：
-*    1）前序遍历，深度优先搜索，每个节点都会遍历到，每层节点最终都是从左到后按序访问
+*    1）前序遍历，深度优先搜索，每个节点都会遍历到，每层节点最终都是从左到右按序访问
 *    2）记录节点所在层的深度，每到新的一层就创建一个新的子列表，层的深度对应子列表的索引，节点值层序存放
 * */
 class Solution {
diff --git a/leetcode_Java/Solution0103.java b/leetcode_Java/Solution0103.java
@@ -0,0 +1,55 @@
+// 103. 二叉树的锯齿形层序遍历
+
+
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
+ * }
+ */
+
+
+/*
+102.二叉树的层序遍历，加上是否反转标记，奇数层不变，偶数层反转子数组
+ */
+class Solution {
+    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
+        List<List<Integer>> list = new ArrayList<>();
+        if (root == null) {
+            return list;
+        }
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.add(root);
+        boolean flag = false;
+        while (!queue.isEmpty()) {
+            int count = queue.size();
+            List<Integer> sonList = new ArrayList<>();
+            while (count > 0) {
+                TreeNode node = queue.remove();
+                sonList.add(node.val);
+                if (node.left != null) {
+                    queue.add(node.left);
+                }
+                if (node.right != null) {
+                    queue.add(node.right);
+                }
+                count--;
+            }
+            if (flag) {
+                Collections.reverse(sonList);
+            }
+            list.add(sonList);
+            flag = !flag;
+        }
+        return list;
+    }
+}
