LeetCode第102题107题 二叉树的层次遍历 — 一招鲜吃遍天~

本文主要是介绍LeetCode第102题107题 二叉树的层次遍历 — 一招鲜吃遍天~，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不是很理解，同样是二叉树的层次遍历问题， 102题是Medium ，107题是 Easy 😂 多年的强迫症又犯了😭

LeetCode第 102 题 题目(Medium)：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

LeetCode第 107 题 题目(Easy)：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

说在前面：

树的遍历问题无非两种方法：

• 深度优先遍历（DFS）：从根节点开始一直到达某个叶子节点，然后再返回根节点到达另一个分支。（根据根节点、左孩子、右孩子的相对顺序分为先序遍历，中序遍历和后序遍历）
• 广度优先遍历（BFS）：一层层的访问树，高层次的节点比低层次的节点先被访问到。

解题思路:

1. 创建List<List>集合，存放result；（泛型List用于存储每一层的节点）

2. 使用Queue存放本层的节点，使用List接收队列每次存放的值

3. 如果当前节点有孩子节点，把孩子节点入队，再放入List中

4. 将List放入List<List>中

小名拿第102题示例来给大家模拟下待会code的过程：

二叉树：[3,9,20,null,null,15,7],

    3/ \9  20/  \15   7

层数	Size	Queue	Node	List
第一层	1	[3] [9] [20]	[3]	[3]
第二层	2	[9] [20] [15] [7]	[9]	[3] [9]
		[9] [20] [15] [7]	[20]	[3] [9] [20]
第三层	2	[15] [7]	[15]	[3] [9] [20] [15]
		[15] [7]	[7]	[3] [9] [20] [15] [7]

Coding~

102 题

 public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> level = new ArrayList<>();//存放每一层的节点for(int i = 0 ; i < size ; i++){TreeNode poll = queue.poll();level.add(poll.val);//将队列pop出来的节点，存到list中if(poll.left != null) queue.add(poll.left);//将左孩子add到队列中if(poll.right != null) queue.add(poll.right);//将有孩子add到队列中}result.add(level);}return result;}

107 题

public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if(root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();//每一层有几个节点List<Integer> level = new ArrayList<>();//用于存放每一层的节点for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();level.add(poll.val);//将队列pop出来的节点，存到list中if (poll.left != null) queue.add(poll.left);//将左孩子add到队列中if (poll.right != null) queue.add(poll.right);//将有孩子add到队列中}//指定每一层的集合都加在 0 这个位置，保证最后一层在最前面result.add(0,level);}return result;
}

注意！

上面的code只有一处不同，就是在于result.add(level);和result.add(0,level);的区别

在源码中List的add方法：

/*** Appends the specified element to the end of this list (optional* operation).** <p>Lists that support this operation may place limitations on what* elements may be added to this list.  In particular, some* lists will refuse to add null elements, and others will impose* restrictions on the type of elements that may be added.  List* classes should clearly specify in their documentation any restrictions* on what elements may be added.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})* @throws UnsupportedOperationException if the <tt>add</tt> operation*         is not supported by this list* @throws ClassCastException if the class of the specified element*         prevents it from being added to this list* @throws NullPointerException if the specified element is null and this*         list does not permit null elements* @throws IllegalArgumentException if some property of this element*         prevents it from being added to this list*/
boolean add(E e);

/*** Inserts the specified element at the specified position in this list* (optional operation).  Shifts the element currently at that position* (if any) and any subsequent elements to the right (adds one to their* indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws UnsupportedOperationException if the <tt>add</tt> operation*         is not supported by this list* @throws ClassCastException if the class of the specified element*         prevents it from being added to this list* @throws NullPointerException if the specified element is null and*         this list does not permit null elements* @throws IllegalArgumentException if some property of the specified*         element prevents it from being added to this list* @throws IndexOutOfBoundsException if the index is out of range*         (<tt>index &lt; 0 || index &gt; size()</tt>)*/
void add(int index, E element);

我们可以看出：add(E e)将指定的元素添加到此列表的尾部。而add(int index,E element) 将指定的元素插入此列表中的指定位置。

最后我们来测试一下吧~

public static void main(String[] args) {TreeNode treeNode = new TreeNode(3);treeNode.left = new TreeNode(9);treeNode.right = new TreeNode(20);treeNode.right.left = new TreeNode(15);treeNode.right.right = new TreeNode(7);levelOrder order = new levelOrder();List<List<Integer>> lists = order.levelOrder(treeNode);/*levelOrderBottom order = new levelOrderBottom();List<List<Integer>> lists = order.levelOrderBottom(treeNode);*/System.out.println(lists);
}

这篇关于LeetCode第102题107题 二叉树的层次遍历 — 一招鲜吃遍天~的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---