算法通关村第六村-USB迷|专注于互联网分享

算法通关村第六村

大家好我是苏麟 , 今天说说数的层序遍历 .

层次遍历简介

广度优先在面试里出现的频率非常高，整体属于简单题，但是很多人面试遇到时就直接放弃了，实在可惜。我们本章就集中研究一下到底难在哪里。

广度优先又叫层次遍历，基本过程如下 :

层次遍历就是从根节点开始，先访问根节点下面一层全部元素，再访问之后的层次，类似金字塔一样一层层访问。我们可以看到这里就是从左到右一层一层的去遍历二叉树，先访问3，之后访问3的左右子孩子5和4，之后分别访问5 和4的左右子孩子[7,6]和[9]，最后得到结果[3,5,4,7,6,9]。

这里的问题是怎么将遍历过的元素的子孩子保存一下呢，使用队列来存储能完美解决上述问题，例如上面的图中:

首先3入队。
然后3出队，之后将3的左右子孩子5和4 保存到队列中。
之后5出队，将5的左右子孩子7和6入队
之后4出队，将4的右子孩子9入队。
之后 7,6,9分别出队，此时都是叶子结点，只出队就行了

该过程不复杂 .

基本的层次遍历

最简单的层次遍历

我们先看最简单的情况，仅仅遍历并输出全部元素，如下 :

上面的二叉树应输出结果 [3,5,4,7,6,9]，方法上面已经图示了，这里看一下怎么代码实现 ?

List<Integer> simpleTree(TreeNode treeNode){//空则返回if(treeNode == null){return new ArrayList<>();}//存放数字List<Ineteger> list = new ArrayList<>();//存放节点Queue<TreeNode> queue = new LinkedList<>();queue.add(treeNode);while(queue.size() > 0){TreeNode temp = queue.remove();list.add(temp.val);if(temp.left != null){queue.add(temp.left);}if(temp.left != null){queue.add(temp.right);}}return list;
}

根据树的结构可以看到，一个结点在一层访问之后，其子孩子都是在下层按照FIFO的顺序处理的，因此队列就是一个缓存的作用。

分层的层序遍历

描述 :

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

题目 :

LeetCode 二叉树的层序遍历 :

102. 二叉树的层序遍历

分析 :

我们可以根据流程图看看 , 先将根节点放到队列中，然后不断遍历队列。那如何判断某一层访问完了呢?

简单，用一个变量size标记一下就行了，size表示某一层的元素个数，只要出队，就将size减1，减到0就说明该层元素访问完了。当size变成0之后，这时队列中剩余元素的个数恰好就是下一层元素的个数，因此重新将size标记为下一层的元素个数就可以继续处理新的一行了

解析 :

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<List<Integer>>();//如果root为空就返回[] , 如果少了这一步null也是会存入队列中的if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for (int i = 1; i <= currentLevelSize; ++i) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}ret.add(level);}return ret;}
}

下面的题输出正好和这道题相反 , 一起看看吧 !

自下向上层序遍历

描述 :

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题目 :

LeetCode 二叉树的层序遍历 :

107. 二叉树的层序遍历 II

分析 :

这里可以使用栈啊,但是为了降低在结果列表的头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构，在链表头部添加一层节点值的列表的时间复杂度是 O(1)。在 Java 中，由于我们需要返回的 List 是一个接口，这里可以使用链表实现。

解析 :

/*** 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;*     }* }*/
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> list = new LinkedList<>();if(root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size() > 0){List<Integer> x = new ArrayList<>();int num = queue.size();for(int i = 1;i <= num ; i++){TreeNode temp = queue.remove();x.add(temp.val);if(temp.left != null){queue.add(temp.left);}if(temp.right != null){queue.add(temp.right);}}list.add(0,x);}return list;}
}

锯齿形层序遍历

描述 :

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

题目 :

LeetCode 二叉树的锯齿形层序遍历 :

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

分析 :

这个题也是102的变种，只是最后输出的要求有所变化，要求我们按层数的奇偶来决定每一层的输出顺序如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。这里只要采用以102 题的思想，为了满足题目要求的返回值为[先从左往右，再从右往左] 交替输出的锯齿形，可以利用双端队列 , 当然也可以头插 .

解析 :

/*** 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;*     }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> list = new LinkedList<>();if(root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);boolean flag = true;while(!queue.isEmpty()){List<Integer> temp = new LinkedList<>();int size = queue.size();for(int i = 0;i < size;i++){TreeNode p = queue.remove();if(flag){//正常插入temp.add(p.val);}else{//头插temp.add(0,p.val);}if(p.left != null){queue.add(p.left);}if(p.right != null){queue.add(p.right);}}flag = !flag;list.add(temp);}return list;}
}

N叉树的层序遍历

描述 :

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

题目 :

LeetCode N叉树的层序遍历 :

429. N 叉树的层序遍历

分析 :

这个也是102的扩展，很简单的广度优先，与二叉树的层序遍历基本一样，借助队列即可实现。

解析 :

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> list = new LinkedList<>();if(root == null){return list;}Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){List<Integer> temp = new ArrayList<>();int size = queue.size();for(int i = 0;i < size;i++){Node p = queue.remove();temp.add(p.val);for(Node y:p.children){queue.add(y);}}list.add(temp);}return list;}
}

处理每层元素的题目

在每个树行中找最大值

描述 :

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

题目 :

LeetCode 在每个树行中找最大值 :

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

分析 :

这里其实就是在得到一层之后使用一个变量来记录当前得到的最大值 , 懂了前面的几道这就是小菜

解析 :

/*** 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;*     }* }*/
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int x = Integer.MIN_VALUE;int size = queue.size();for(int i = 0;i < size ;i++){TreeNode temp = queue.remove();x = Math.max(temp.val,x);if(temp.left != null){queue.add(temp.left);}if(temp.right != null){queue.add(temp.right);}}list.add(x);} return list;}
}

当然这个会了 , 求每层最小值也会了

二叉树的右视图

描述 :

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

题目 :

LeetCode 二叉树的右视图 :

199. 二叉树的右视图

分析 :

这个题目出现频率还挺高的，如果没有提前思考过，面试现场可能会想不到怎么做。其实也很简单那，利用 BFS（Breadth First Search）广度优先算法 , 进行层次遍历，记录下每层的最后一个元素。

这里可能有个小坑啊 : 如果是下图这么画的输出的就是[1,3,4]

解析 :

/*** 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;*     }* }*/
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();for(int i = 0;i < size ; i++){TreeNode temp = queue.remove();if(temp.left != null){queue.add(temp.left);}if(temp.right != null){queue.add(temp.right);}if( i == size -1){list.add(temp.val);}}}return list;}
}

右视图会了 , 左视图就会了

找树左下角的值

描述 :

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

题目 :

LeetCode 找树左下角的值 :

513. 找树左下角的值

分析 :

我们继续观察层次遍历的执行过程 :

我们可以发现，正常执行层次遍历，不管最底层有几个元素，最后一个输出的一定是是最底层最右的元素，那这里我们就想了，能否先存入右节点再存入左节点最后一个就输出左边的呢 ? 是的，这就是解决本题的关键。

解析 :

/*** 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;*     }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.add(root); int x = 0;while(!queue.isEmpty()){TreeNode temp = queue.remove();x = temp.val;if(temp.right != null){queue.add(temp.right);}if(temp.left != null){queue.add(temp.left);}}return x;}
}

这期就到这里 , 下一关见!