算法通关村第6关【白银】| 树的层次遍历问题

一、基本层次遍历问题

1.二叉树的层次遍历

思路：使用队列可以很好的保存遍历状态，出队将结点左右子结点入队，用size记录下一层的元素个数，这样就能区分出层了 

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();while(size>0){TreeNode node = queue.remove();list.addLast(node.val);if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(list);}return res;}
}

2.二叉树的层次遍历II

 思路：此题和上一题大同小异，只需要在添加结果集的时候头插法就可以了。

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> list = new LinkedList<>();while(size>0){TreeNode node = queue.removeFirst();size--;list.add(node.val);if(node.left!= null){queue.add(node.left);}if(node.right!= null){queue.add(node.right);}}res.add(0,list);}return res;}
}

3.锯齿形遍历 

思路：和层次遍历不同的是每层顺序奇偶方向交替，用一个变量记录当前层的变量规则，从左往右就是尾插法，从右往左就是头插法

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int loop = 1;while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();for(int i = 0;i<size;i++){TreeNode node = queue.removeFirst();if(node.left!= null){queue.add(node.left);}   if(node.right!= null){queue.add(node.right);}if(loop%2==0){list.addFirst(node.val);}else{list.add(node.val);}}res.add(list);loop++;}return res;}
}

4.N叉树的层次遍历

 思路：此题和基本层次遍历不同的是，每次不是添加左右孩子入队而是添加孩子列表入队，把添加左右孩子替换成遍历添加列表就成。

class Solution {public List<List<Integer>> levelOrder(Node root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<Node> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();while(size>0){Node node = queue.remove();list.addLast(node.val);for(Node child : node.children){queue.add(child);}size--;}res.add(list);}return res;}
}

二、处理每层元素的问题

1.在每个树行中找最大值

思路：还是和遍历大同小异，现在不是将所有子结点都加入结果，只取每层最大的，比较一下就行

class Solution {public List<Integer> largestValues(TreeNode root) {if(root == null){return new LinkedList<>();}List<Integer> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();int max = Integer.MIN_VALUE;while(size>0){TreeNode node = queue.remove();if(node.val>max){max = node.val;}if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(max);}return res;}
}

 2.每个树行的平均值

 思路：和上一题找最大值没什么差别，每层相加除以size就可以。

class Solution {public List<Double> averageOfLevels(TreeNode root) {if(root == null){return new LinkedList<>();}List<Double> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();Double mean = 0.0;for(int i = 0;i<size;i++){TreeNode node = queue.remove();mean += node.val;if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}}res.add(mean/size);}return res;}
}

3.二叉树的右视图

思路：层次遍历，最后一个元素加入结果集就行。 

class Solution {public List<Integer> rightSideView(TreeNode root) {if(root == null){return new LinkedList<>();}List<Integer> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();TreeNode node = root;while(size>0){node = queue.remove();if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(node.val);}return res;}
}

4.找树最小角的值

思路：1）层次遍历，记录下每层第一个元素

2）从右往左层次遍历，最后一个元素

//方法一
class Solution {public int findBottomLeftValue(TreeNode root) {if(root == null){return -1;}int res = -1;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size()>0){int size = queue.size();res = queue.get(0).val;while(size>0){TreeNode node = queue.remove();size--;if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}}}return res;}
}//方法二
class Solution {public int findBottomLeftValue(TreeNode root) {if(root == null){return -1;}int res = -1;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNode node = queue.poll();res = node.val;if(node.right != null){queue.offer(node.right);}   if(node.left != null){queue.offer(node.left);}}return res;}
}