#yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树

1.简述:

描述

给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)

数据范围:#yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树,树上每个节点的val满足 #yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树要求:空间复杂度:#yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树,时间复杂度:#yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树

例如:

给定的二叉树是{1,2,3,#,#,4,5}

#yyds干货盘点# 面试必刷TOP101:按之字形顺序打印二叉树

该二叉树之字形层序遍历的结果是

[

[1],

[3,2],

[4,5]

]

示例1

输入:

{1,2,3,#,#,4,5}

返回值:

[[1],[3,2],[4,5]]

说明:

如题面解释,第一层是根节点,从左到右打印结果,第二层从右到左,第三层从左到右。

示例2

输入:

{8,6,10,5,7,9,11}

返回值:

[[8],[10,6],[5,7,9,11]]

示例3

输入:

{1,2,3,4,5}

返回值:

[[1],[3,2],[4,5]]
public class Solution {
public ArrayList Print(TreeNode pRoot) {
Deque deque = new LinkedList<>();
ArrayList res = new ArrayList<>();
if(pRoot != null) deque.add(pRoot);
while(!deque.isEmpty()) {
// 打印奇数层
ArrayListtmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode node = deque.removeFirst();
tmp.add(node.val);
// 先左后右加入下层节点
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
res.add(tmp);
if(deque.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode node = deque.removeLast();
tmp.add(node.val);
// 先右后左加入下层节点
if(node.right != null) deque.addFirst(node.right);
if(node.left != null) deque.addFirst(node.left);
}
res.add(tmp);
}
return res;
}

}
发表评论

相关文章