102.二叉树的层序遍历(广度优先遍历BFS----Breadth_First_Search)

题目:

思路1：迭代

利用广度优先遍历的思想，用一个队列来做到层序遍历
队列不为空时，每次循环对当前层的节点数做操作，并确定下一层节点

代码1：

/*** 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>> ans = new ArrayList<List<Integer>>();Deque<TreeNode> deque = new LinkedList<TreeNode>();if(root == null)return ans;deque.offer(root);while(!deque.isEmpty()){List<Integer> level_ans = new ArrayList<Integer>();int len =deque.size();//确定每层的个数for(int i = 0;i < len;i++){//提出当前层，确定下一层TreeNode node = deque.poll();level_ans.add(node.val);if(node.left != null)deque.offer(node.left);if(node.right != null)deque.offer(node.right);}ans.add(level_ans);}return ans;}
}

复杂度分析：

时间复杂度：O（n）
空间复杂度：O（n）

思路2：递归

需要不断传递一个index值，来确定当前的层
并且当前层>二维列表.size()时,增加一个子列表来存放当前层的节点

代码：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<List<Integer>>();int index = 0;//用来记录当前节点的层度level_recursion(root,index+1,ans);//第一层return ans;}public void level_recursion(TreeNode node,int index,List<List<Integer>> ans){if(node == null)return;if(ans.size() < index)ans.add(new ArrayList<Integer>());ans.get(index-1).add(node.val);level_recursion(node.left,index+1,ans);level_recursion(node.right,index+1,ans);}
}