Merge pull request gzc426#333 from Syuan-Cheng/master

gzc426 · web-flow · commit 4586546b1df0 · 2018-12-06T22:08:37.000+08:00
syuan
diff --git a/2018.12.05-leetcode102/syuan.md b/2018.12.05-leetcode102/syuan.md
@@ -0,0 +1,95 @@
+##### 题目
+```
+给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
+
+例如:
+给定二叉树: [3,9,20,null,null,15,7],
+
+    3
+   / \
+  9  20
+    /  \
+   15   7
+
+返回其层次遍历结果：
+
+[
+  [3],
+  [9,20],
+  [15,7]
+]
+
+
+```
+##### 代码
+循环
+```
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<List<Integer>> levelOrder(TreeNode root) {
+        List<List<Integer>> resList=new ArrayList<>();
+        Queue<TreeNode> queue=new LinkedList<>();
+        if (root==null) {
+            return resList;
+        }
+
+        queue.offer(root);
+        while(!queue.isEmpty()){
+            int length=queue.size();
+            List<Integer> tempList=new ArrayList<>();
+            for (int i=0; i<length; i++) {
+                if (queue.peek().left!=null) {
+                    queue.offer(queue.peek().left);
+                }
+                if (queue.peek().right!=null) {
+                    queue.offer(queue.peek().right);
+                }
+                tempList.add(queue.poll().val);
+            }
+            resList.add(tempList);
+        }
+        return resList;
+    }
+}
+```
+递归
+
+```
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<List<Integer>> levelOrder(TreeNode root) {
+        List<List<Integer>> res = new ArrayList<List<Integer>>();
+        levelOrderHelper(res, root, 0);
+        return res;
+    }
+
+    public void levelOrderHelper(List<List<Integer>> res,TreeNode root,int length){
+        if (root==null) {
+            return;
+        }
+        if (length>=res.size()) {
+            res.add(new ArrayList<Integer>());
+        }
+        res.get(length).add(root.val);
+        levelOrderHelper(res,root.left,length+1);
+        levelOrderHelper(res,root.right,length+1);
+    }
+
+}
+```
diff --git a/2018.12.06-leetcode103/syuan.md b/2018.12.06-leetcode103/syuan.md
@@ -0,0 +1,98 @@
+##### 题目
+
+```
+给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
+
+例如：
+给定二叉树 [3,9,20,null,null,15,7],
+
+    3
+   / \
+  9  20
+    /  \
+   15   7
+
+返回锯齿形层次遍历如下：
+
+[
+  [3],
+  [20,9],
+  [15,7]
+]
+```
+#### 代码
+##### 两个栈
+
+```
+class Solution {
+    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
+        List<List<Integer>> resList=new ArrayList<>();
+        Stack<TreeNode> stack1=new Stack<>();
+        Stack<TreeNode> stack2=new Stack<>();
+        if (root==null) {
+            return resList;
+        }
+
+        stack1.push(root);
+        int index=1;
+        while(!stack1.isEmpty() || !stack2.isEmpty()){
+            int length1=stack1.size();
+            int length2=stack2.size();
+            List<Integer> tempList=new ArrayList<>();
+            if (index%2!=0) {
+                for (int i=0; i<length1; i++) {
+                    if (stack1.peek().left!=null) {
+                        stack2.push(stack1.peek().left);
+                    }
+                    if (stack1.peek().right!=null) {
+                        stack2.push(stack1.peek().right);
+                    }
+                    tempList.add(stack1.pop().val);
+                }
+                index++;
+            }else{
+                for (int i=0; i<length2; i++) {
+                    if (stack2.peek().right!=null) {
+                        stack1.push(stack2.peek().right);
+                    }
+                    if (stack2.peek().left!=null) {
+                        stack1.push(stack2.peek().left);
+                    }
+                    tempList.add(stack2.pop().val);
+                }
+                index++;
+            }
+            
+            resList.add(tempList);
+        }
+        return resList;
+    }
+}
+```
+##### 递归
+
+```
+class Solution {
+    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
+        List<List<Integer>> res=new ArrayList<>();
+        zigzagLevelOrderHelp(res,root,0);
+        return res;
+    }
+
+    public void zigzagLevelOrderHelp(List<List<Integer>> res,TreeNode root,int index){
+        if (root==null) return;
+
+        if (res.size()<=index) {
+            res.add(new ArrayList<>());
+        }
+        if (index%2==0) {
+            res.get(index).add(root.val);
+        }else{
+            res.get(index).add(0,root.val);
+        }
+        zigzagLevelOrderHelp(res,root.left,index+1);
+        zigzagLevelOrderHelp(res,root.right,index+1);
+    }
+}
+```
+> add(index,int) 该函数可以对一个数组进行前序插入  其余的会往后挪动
