LeetCode高频题:二叉树的锯齿形(Z字形,之字形)层序遍历
LeetCode高频题:二叉树的锯齿形(Z字形,之字形)层序遍历
提示:本题是系列LeetCode的150道高频题,你未来遇到的互联网大厂的笔试和面试考题,基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们,吃完饭就是设计考题,然后去考应聘人员,你要做的就是学基础树结构与算法,然后打通任督二脉,以应对波云诡谲的大厂笔试面试题!
你要是不扎实学习数据结构与算法,好好动手手撕代码,锻炼解题能力,你可能会在笔试面试过程中,连题目都看不懂!比如华为,字节啥的,足够让你读不懂题
题目
给定一个二叉树,返回该二叉树的之字形层序遍历,
第一层从左往右,下一层从右向左,一直这样交替
数据返回:0<=n<=1500,树上每个节点的val满足|val|<=1500
要求,空间复杂度o(n),时间复杂度o(n)
LeetCode本题连接,LeetCode那个你看看题目就行
写代码按我的写,不要装进list,因为互联网长达的笔试不会让你装list
而是直接打印序列
一、审题
示例:
普通二叉树BFS按层遍历,每次都是从左往右打印
平时,正常层序遍历的话,就是队列依次加节点,节点的左右子不空加就行
【1】二叉树的宽度优先遍历BFS:按层的遍历方式,请你用队列实现DFS,或者请你用栈实现BFS
当时层序遍历是BFS搞定的,一个队列不断加左右子:
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value = v;
}
}
//构造一颗树,今后方便使用
public static Node generateBinaryTree(){
//树长啥样呢
// 1
// 2 3
// 4 5 6 7
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
head.left = n2;
head.right = n3;
Node n4 = new Node(4);
Node n5 = new Node(5);
n2.left = n4;
n2.right = n5;
Node n6 = new Node(6);
Node n7 = new Node(7);
n3.left = n6;
n3.right = n7;
return head;
}
//复习:这样做,最开始将head加入队列
//开始循环操作:弹出打印。
// 然后看其左右子是否不为null,是就加入队列,否则不管。
public static void bfsBinaryTreePrint(Node head){
if (head == null) return;
LinkedList<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()){
Node cur = queue.poll();
System.out.print(cur.value + " ");
//按层加入左右子
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
//图也是这么干BFS,DFS就是用栈,一条道走到黑
}
public static void test(){
Node cur = generateBinaryTree();
BreadthFirstSearch(cur);
bfsBinaryTreePrint(cur);
}
public static void main(String[] args){
test();
}
之字形遍历就和上面一点点的区别,直接用上面代码改编就行
这个之字形,实际上还是层序遍历的框架,唯一不同的是:
(1)当你在第1层遍历时,加的顺序应该是右子,左子,从右往左加,这样下次打印才是从右往左打印的
(2)当你在第2层遍历时,加的顺序应该是左子,右子,从左往右加,这样下次打印才是从左往右打印的
……
依次类推
你在奇数层,则加的顺序是右子左子
你在偶数层,则加的顺序是左子右子
整个思想超级简单
咱们直接改编BFS普通层序遍历(从左往右)代码来玩:
//二叉树之字形遍历
public static List<List<Integer>> bfsZigzagPrint(TreeNode head){
if (head == null) return null;
LinkedList<TreeNode> queue = new LinkedList<>();//BFS的重要结构
queue.add(head);
//用一个哈希表记录二叉树每个节点的层数
HashMap<TreeNode, Integer> map = new HashMap<>();//node--层
map.put(head, 1);//奇数层
List<List<Integer>> ans = new ArrayList<>();//结果
while (!queue.isEmpty()){
//奇数层从尾部插入,偶数层从头插入
List<Integer> tmp = new ArrayList<>();//单独处理一个层的那些节点
int size = queue.size();//目前这一串——全部处理完,咱们才能接着处理别的
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
int level = map.get(cur);//拿到层数
// System.out.print(cur.value + " ");//弹出打印cur.val
//按层——看层数是奇数还是偶数
if ((level & 1) == 1) {//奇数层,只能从右往左加——放tmp的屁股
tmp.add(cur.value);
}else {//偶数层,从左往右家,放tmp头部
tmp.add(0, cur.value);
}
//正常放节点到队列
if (cur.left != null) {
queue.add(cur.left);
map.put(cur.left, level + 1);
}
if (cur.right != null) {
queue.add(cur.right);
map.put(cur.right, level + 1);
}
}
ans.add(tmp);//每次队列中一串搞定,tmp放ans
}
//图也是这么干BFS,DFS就是用栈,一条道走到黑
return ans;
}
代码完全就是普通bfs改编来的哦
测试:
public static void test(){
TreeNode cur = generateBinaryTree();
BreadthFirstSearch(cur);
bfsBinaryTreePrint(cur);
System.out.println();
//树长啥样呢
// 1
// 2 3
// 4 5 6 7
TreeNode cur2 = generateBinaryTree();
List<List<Integer>> ans = bfsZigzagPrint(cur2);
for(List<Integer> list : ans){
for(Integer i : list) System.out.print(i + " ");
}
}
public static void main(String[] args){
test();
}
结果:
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 3 2 4 5 6 7
第三行就是zigzag打印
之字形层序遍历
LeetCode那个题目很狗
它要你把结果,按层放入列表,算了吧
咱们考题,会让你直接打印序列
就像我这样就行,很简单的
本题到此OK了
还是测一下leetcode:
代码:
/**
* 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>> ans = new ArrayList<>();//结果
if (root == null) return ans;
LinkedList<TreeNode> queue = new LinkedList<>();//BFS的重要结构
queue.add(root);
//用一个哈希表记录二叉树每个节点的层数
HashMap<TreeNode, Integer> map = new HashMap<>();//node--层
map.put(root, 1);//奇数层
while (!queue.isEmpty()){
//奇数层从尾部插入,偶数层从头插入
List<Integer> tmp = new ArrayList<>();//单独处理一个层的那些节点
int size = queue.size();//目前这一串——全部处理完,咱们才能接着处理别的
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
int level = map.get(cur);//拿到层数
// System.out.print(cur.value + " ");//弹出打印cur.val
//按层——看层数是奇数还是偶数
if ((level & 1) == 1) {//奇数层,只能从右往左加——放tmp的屁股
tmp.add(cur.val);
}else {//偶数层,从左往右家,放tmp头部
tmp.add(0, cur.val);
}
//正常放节点到队列
if (cur.left != null) {
queue.add(cur.left);
map.put(cur.left, level + 1);
}
if (cur.right != null) {
queue.add(cur.right);
map.put(cur.right, level + 1);
}
}
ans.add(tmp);//每次队列中一串搞定,tmp放ans
}
//图也是这么干BFS,DFS就是用栈,一条道走到黑
return ans;
}
}
结果:
总结
提示:重要经验:
1)普通的bfs二叉树层序遍历,非常简单,字节将队列不断从左往右加就行了
2)本题就是从1)改变来的,bfs队列控制,奇数层的时候,让加入队列的顺序从右往左,偶数层的时候,加入队列从左往右
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。
相关文章
- [LeetCode] Binary Tree Level Order Traversal 二叉树层次遍历(DFS | BFS)
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 344 反转字符串
- Java实现 LeetCode 199 二叉树的右视图
- Java实现 LeetCode 199 二叉树的右视图
- Java实现 LeetCode 145 二叉树的后序遍历
- Java实现 LeetCode 111 二叉树的最小深度
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- LeetCode: 102_Binary Tree Level Order Traversal | 二叉树自顶向下的层次遍历 | Easy
- LeetCode:94_Binary Tree Inorder Traversal | 二叉树中序遍历 | Medium
- LeetCode:145_Binary Tree Postorder Traversal | 二叉树后序遍历 | Hard
- [LeetCode] Valid Anagram
- 【二叉树】LeetCode 102. 二叉树的层序遍历【中等】
- (“树” 之 前中后序遍历 ) 94. 二叉树的中序遍历 ——【Leetcode每日一题】
- ( “树” 之 DFS) 101. 对称二叉树 ——【Leetcode每日一题】
- 【Leetcode刷题Python】199. 二叉树的右视图
- 【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
- 【LeetCode】543. 二叉树的直径
- 【LeetCode】103. 二叉树的锯齿形层序遍历
- 【LeetCode】剑指 Offer II 047. 二叉树剪枝