剑指offer32----之字形打印一颗二叉树
2024-10-06 23:00:22
题目
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路
在这里我们如果单纯的使用队列去弄的话，会很麻烦，所有这里我们使用栈结构来实现，如下图所示，我们打印的顺序应该是：1、3、2、4、5、6。
（1）我们先把1压入到一个栈（stack1），然后取出1，这时我们把他的左右节点放到另一个栈里（stack2），因为是先打印3再2，所以我们应该从左到右压。
（2）我们拿到刚才压2和3的栈（stack2），因为3在栈顶，所以先取出3打印，然后打印2，打印的同时也要把当前节点左右节点压入到另一个栈（stack1），因为先取出的是3，所以我们把3的左子节点压入栈，然后再压2的子节点，因为是打印顺序是456，所以我们从右到左。
如果当两个栈都为空时，代表当前所有的节点都打印完了，所以结束。
代码如下：
public class Offer32 {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static void printTree(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
int index = 2;
stack1.push(root);
while (stack1.size() > 0 || stack2.size() > 0) {
TreeNode cur = null;
while (index % 2 == 0 && stack1.size() > 0) {
// stack2负责压入层数为偶数的节点
cur = stack1.pop();
System.out.println("树节点" + cur.val);
// 先压左再压右
if (cur.left != null) {
stack2.push(cur.left);
}
if (cur.right != null) {
stack2.push(cur.right);
}
}
while (index % 2 != 0 && stack2.size() > 0) {
// stack1负责压入层数为奇数的节点
cur = stack2.pop();
System.out.println("树节点" + cur.val);
// 先压右再压左
if (cur.right != null) {
stack1.push(cur.right);
}
if (cur.left != null) {
stack1.push(cur.left);
}
}
index++;
}
}
}
最新文章
- 算法入门笔记------------Day4
- sed 指令
- CSS“反转”为LESS
- POJ3267 The Cow Lexicon(dp)
- vmware9安装centos和Mac经验总结
- st-Spanning Tree
- Python之路： 模版篇
- 我眼中的ASP.NET Core之微服务
- java快速排序详解
- C语言实现二叉树的基本操作
- Day3--------------目录文件的浏览、管理及维护
- 关于Jedis是否线程安全的测试
- fisheye Error occurred during initialization of VM Could not reserve enough space for object heap 问题解决!
- 设置ubuntu 终端显示路径长度
- asp.net 网站在Apache下的配置,就这么简单
- 第三篇 Python关于mysql的API--pymysql模块， mysql事务
- 20145328 《Java程序设计》实验二实验报告
- thinkphp5集成微信支付【公众号支付】快捷路径
- Python入门-初始函数
- 关于JavaScript的push()函数