按之字形顺序打印二叉树
2023-02-18 16:26:31 时间
/**
* 题目描述
* 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
* 示例1
* 输入
* {8,6,10,5,7,9,11}
* 返回值
* [[8],[10,6],[5,7,9,11]]
*/
思路:
两个栈来实现; 定义一个放奇数层得栈,一个方偶数层得栈,和一个层奇偶标志, 遍历两个栈,每次消灭一个栈中得数据,添加在list中添加一层得数据 需要注意得是结合栈得先进后出性质,当我们遍历到奇数层时候,我们要从左到右得添加数据到栈二.同理偶数相反.
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> datas = new ArrayList<>();
if (pRoot == null) {
return datas;
}
//奇数行从左到右,偶数行从右到左
//奇数栈
Stack<TreeNode> oddStack = new Stack<>();
//偶数栈
Stack<TreeNode> evenStack = new Stack<>();
oddStack.add(pRoot);
//当前需要遍历的是奇数栈
boolean isOdd = true;
while (!oddStack.isEmpty() || !evenStack.isEmpty()) {
ArrayList<Integer> item = new ArrayList<>();
if (isOdd) {
while (!oddStack.isEmpty()) {
final TreeNode poll = oddStack.pop();
item.add(poll.val);
if (poll.left != null) {
evenStack.push(poll.left);
}
if (poll.right != null) {
evenStack.push(poll.right);
}
}
} else {
while (!evenStack.isEmpty()) {
while (!evenStack.isEmpty()) {
final TreeNode poll = evenStack.pop();
item.add(poll.val);
if (poll.right != null) {
oddStack.add(poll.right);
}
if (poll.left != null) {
oddStack.add(poll.left);
}
}
}
}
isOdd = !isOdd;
datas.add(item);
}
return datas;
}
相关文章
- Java编程中忽略这些细节,Bug肯定找上你
- 9个问题,带你掌握流程控制语句中的java原理
- 从IDC Marketscape报告看区块链政务数字化未来:权威解读新热点、新机遇
- chatGPT的火爆,并不偶然
- React 开发 | 常用 Hooks
- JDK19都出来了~是时候梳理清楚JDK的各个版本的特性了【JDK12特性讲解】
- Eolink 让我“重新认识“了自动化测试...
- 老板:你也把咱们网站弄成灰色——网站变灰色如何实现
- iptables规则案例
- ‘极锐’-一种新的锐化算法
- PS/LR滤镜插件套装 Nik Collection v5.3.0 Win/Mac
- Chrome插件:uBlock Origin – Chrome浏览器高效低占用的广告拦截插件
- 前端与区块链
- 云原生之微服务
- 集群动态环境管理神器 Modules
- 记 os_object_release Crash 排查
- 记 libAccessibility 通知 Crash 排查
- Ant Design Pro 中 点击子菜单的时候,其他菜单不自动收起来
- ETC 可视化
- 1267-Illegal mix of collations (utf8mb4_general_ci,IMPLICIT) and (utf8mb4_0900_ai_ci,IMPLIC for o...