Merge pull request gzc426#334 from symkmk/master

gzc426 · web-flow · commit 623b35bcd9d7 · 2018-12-06T22:08:58.000+08:00
leetcode_102二叉树的层次遍历
diff --git a/2018.12.05-leetcode102/妮可.md b/2018.12.05-leetcode102/妮可.md
@@ -0,0 +1,166 @@
+```java
+package sy181205;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+
+
+
+
+/**
+ * @author suyuan
+ *	
+给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
+
+例如:
+给定二叉树: [3,9,20,null,null,15,7],
+
+    3
+   / \
+  9  20
+    /  \
+   15   7
+返回其层次遍历结果：
+
+[
+  [3],
+  [9,20],
+  [15,7]
+]
+
+
+ */
+public class leetcode_102二叉树的层次遍历
+{
+
+	public static void main(String[] args)
+	{
+		TreeNode node1=new TreeNode(1);
+		TreeNode node2=new TreeNode(2);
+		TreeNode node3=new TreeNode(3);
+		TreeNode node4=new TreeNode(4);
+		TreeNode node5=new TreeNode(5);
+	
+		node1.left=node2;
+		node1.right=node3;
+		
+		node2.left=node4;
+		node2.right=node5;
+	
+		node3.left=null;
+		node3.right=null;
+		
+		node4.left=null;
+		node4.right=null;
+		node5.left=null;
+		node5.right=null;
+	
+//		List<List<Integer>> resList=levelOrder(node1);
+		List<List<Integer>> resList=levelOrder3(node1);
+		for (List<Integer> list : resList)
+		{
+			for (Integer integer : list)
+			{
+				System.out.print(integer+" ");
+			}
+			System.out.println();
+		}
+		
+		
+
+	}
+	
+	 public static List<List<Integer>> levelOrder(TreeNode root)
+	 {
+		 	List<List<Integer>> result=new ArrayList<List<Integer>>();
+		 	if(root==null)
+			 	return result;
+		 	Queue<TreeNode> queue=new LinkedList<TreeNode>();
+		    queue.add(root);
+		    TreeNode node=null;
+		    
+		    while(!queue.isEmpty())
+		    {
+		    	//高度还是要记的...省不了
+		    	int count=queue.size();
+		    	List<Integer> list=new ArrayList<>();
+		    	while(count>0)
+		    	{
+		    	node=queue.poll();
+		    	list.add(node.val);
+		    	if(node.left!=null )
+		    		queue.add(node.left);
+		    	if(node.right!=null)
+		    		queue.add(node.right);
+		    	count--;
+		    	}
+		    	
+		    	  result.add(list);
+		    }
+		   
+		 return result;
+	 
+	 }
+	 
+	//递归实现
+	    public static List<List<Integer>> levelOrder3(TreeNode root) {
+	        List<List<Integer>> res=new ArrayList<>();
+	        if(root==null)  return res;
+	        recursionLevelOrder(root,0,res);
+	        return res;
+	    }
+	    private static void recursionLevelOrder(TreeNode root,int level,List<List<Integer>> res){
+	        if(root==null) return;
+	        if(res.size()==level){
+	            List<Integer> subres=new ArrayList<>();
+	            subres.add(root.val);
+	            res.add(subres);
+	        }else{
+	            res.get(level).add(root.val);
+	        }
+	        recursionLevelOrder(root.left,level+1,res);
+	        recursionLevelOrder(root.right,level+1,res);
+	    }
+	 
+	 public static List<List<Integer>> levelOrder1(TreeNode root)
+	 {
+		 	List<List<Integer>> result=new ArrayList<List<Integer>>();
+		 	if(root==null)
+			 	return result;
+		 	Queue<TreeNode> queue=new LinkedList<TreeNode>();
+		    queue.add(root);
+		    TreeNode node=null;
+		    
+		    while(!queue.isEmpty())
+		    {
+		    	List<Integer> list=new ArrayList<>();
+		    	while(!queue.isEmpty())
+		    	{
+		    	node=queue.poll();
+		    	list.add(node.val);
+		    	}
+		    	if(node.left!=null && node.right!=null)
+		    		queue.add(node.left);
+		    	if(node.right!=null && node.right!=null)
+		    		queue.add(node.right);
+		    	  result.add(list);
+		    }
+		   
+		 return result;
+	 
+	 }
+	 
+
+}
+
+  class TreeNode {
+     int val;
+     TreeNode left;
+     TreeNode right;
+     TreeNode(int x) { val = x; }
+ }
+```
diff --git a/2018.12.06-leetcode103/妮可.md b/2018.12.06-leetcode103/妮可.md
@@ -0,0 +1,129 @@
+```java
+package sy181206;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+
+
+
+
+/**
+ * @author suyuan
+ * 
+给定一个二叉树，返回其节点值的锯齿形层次遍历。
+（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
+
+例如：
+给定二叉树 [3,9,20,null,null,15,7],
+
+    3
+   / \
+  9  20
+    /  \
+   15   7
+返回锯齿形层次遍历如下：
+
+[
+  [3],
+  [20,9],
+  [15,7]
+]
+
+ */
+public class leetcode_103二叉树的锯齿形层次遍历
+{
+
+	public static void main(String[] args)
+	{
+		TreeNode node1=new TreeNode(1);
+		TreeNode node2=new TreeNode(2);
+		TreeNode node3=new TreeNode(3);
+		TreeNode node4=new TreeNode(4);
+		TreeNode node5=new TreeNode(5);
+	
+		node1.left=node2;
+		node1.right=node3;
+		
+		node2.left=node4;
+		node2.right=node5;
+	
+		node3.left=null;
+		node3.right=null;
+		
+		node4.left=null;
+		node4.right=null;
+		node5.left=null;
+		node5.right=null;
+	
+//		List<List<Integer>> resList=levelOrder(node1);
+		List<List<Integer>> resList=zigzagLevelOrder(node1);
+		for (List<Integer> list : resList)
+		{
+			for (Integer integer : list)
+			{
+				System.out.print(integer+" ");
+			}
+			System.out.println();
+		}
+
+	}
+	
+	  public static List<List<Integer>> zigzagLevelOrder(TreeNode root) 
+	  {
+		  List<List<Integer>> result=new ArrayList<List<Integer>>();
+		 	if(root==null)
+			 	return result;
+		 	Queue<TreeNode> queue=new LinkedList<TreeNode>();
+		    queue.add(root);
+		    TreeNode node=null;
+		    //true从左往右
+		    boolean flag=true;
+		    
+		    while(!queue.isEmpty())
+		    {
+		    	//高度还是要记的...省不了
+		    	int count=queue.size();
+		    	List<Integer> list=new ArrayList<>();
+		    	while(count>0)
+		    	{
+		    	node=queue.poll();
+		    	list.add(node.val);
+		    	if(node.left!=null )
+		    		queue.add(node.left);
+		    	if(node.right!=null)
+		    		queue.add(node.right);
+		    	count--;
+		    	}
+		    	
+		    	if(flag)
+		    	{
+		    	  result.add(list);
+		    	  flag=false;
+		    	}
+		    	else
+		    	{
+		    		Collections.reverse(list);
+		    		result.add(list);
+		    		flag=true;
+		    	}
+		    	
+		    }
+		   
+		 return result;
+	  }
+
+}
+
+class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+    TreeNode(int x) { val = x; }
+}
+
+```
