[剑指Offer]-之字形打印二叉树

2024-06-12 13:58

本文主要是介绍[剑指Offer]-之字形打印二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

解题思路
  • 使用currentlayer记录层数,从一开始计数
  • 当两个栈任意一个不为空时进行循环
  • 弹出当前层栈尾元素,同时层数+1,保存分奇偶保存下一层元素
    在这里插入图片描述
  • 最后需要注意的时打印换行的时机,分奇偶讨论,如果栈空则回退一层。
    在这里插入图片描述
算法图解

在这里插入图片描述

  • 注意代码中对于结束递归的条件的设定!
  • 是否访问数组的赋值!
参考代码:
package offer;import java.util.Stack;/*** 之形打印二叉树*/
public class Offer32_3 {public static void main(String[] args) {BinaryTreeNode root = new BinaryTreeNode(1);BinaryTreeNode node1 = new BinaryTreeNode(2);BinaryTreeNode node2 = new BinaryTreeNode(3);BinaryTreeNode node3 = new BinaryTreeNode(4);BinaryTreeNode node4 = new BinaryTreeNode(5);BinaryTreeNode node5 = new BinaryTreeNode(6);BinaryTreeNode node6 = new BinaryTreeNode(7);BinaryTreeNode node7 = new BinaryTreeNode(8);BinaryTreeNode node8 = new BinaryTreeNode(9);BinaryTreeNode node9 = new BinaryTreeNode(10);BinaryTreeNode node10 = new BinaryTreeNode(11);BinaryTreeNode node11 = new BinaryTreeNode(12);BinaryTreeNode node12 = new BinaryTreeNode(13);BinaryTreeNode node13 = new BinaryTreeNode(14);BinaryTreeNode node14 = new BinaryTreeNode(15);root.leftTree = node1;root.rightTree = node2;node1.leftTree = node3;node3.leftTree = node7;node3.rightTree = node8;node1.rightTree = node4;node4.leftTree = node9;node4.rightTree = node10;node2.rightTree = node6;node6.leftTree = node13;node6.rightTree = node14;node2.leftTree = node5;node5.leftTree = node11;node5.rightTree = node12;printByZ(root);}private static void printByZ(BinaryTreeNode root) {if (root == null) {return;}int currentlayer = 1;Stack<BinaryTreeNode> stackj = new Stack<BinaryTreeNode>();Stack<BinaryTreeNode> stacko = new Stack<BinaryTreeNode>();stackj.push(root);while (!stackj.empty() || !stacko.empty()) {BinaryTreeNode currNode = null;if (currentlayer % 2 == 0 && !stacko.empty()) {currNode = stacko.pop();}if (currentlayer % 2 != 0 && !stackj.empty()) {currNode = stackj.pop();}System.out.print(currNode.node_value + " ");currentlayer++;if (currentlayer % 2 == 0) {if (currNode.leftTree != null) {stacko.push(currNode.leftTree);}if (currNode.rightTree != null) {stacko.push(currNode.rightTree);}} else {if (currNode.rightTree != null) {stackj.push(currNode.rightTree);}if (currNode.leftTree != null) {stackj.push(currNode.leftTree);}}/*** 分奇偶 讨论什么时候打印换行  放在一起判断的话会出现某一个空就打印换行 引起空指针异常*/if (currentlayer % 2 != 0) {if (stacko.empty()) {System.out.println();} else {currentlayer = currentlayer - 1;}} else {if (stackj.empty()) {System.out.println();} else {currentlayer = currentlayer - 1;}}}}
}

附录

该题源码在我的 ?Github 上面!

这篇关于[剑指Offer]-之字形打印二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1054407

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

多数据源的事务处理总是打印很多无用的log日志

之前做了一个项目,需要用到多数据源以及事务处理,在使用事务处理,服务器总是打印很多关于事务处理的log日志(com.atomikos.logging.Slf4jLogger),但是我们根本不会用到这些log日志,反而使得查询一些有用的log日志变得困难。那要如何屏蔽这些log日志呢? 之前的项目是提高项目打印log日志的级别,后来觉得这样治标不治本。 现在有一个更好的方法: 我使用的是log

fastreport打印trichedit分页问题的解决

用fastreport来打印richedit里面的内容。刚开始放一个frxrichview组件到报表上,然后在 var str: TMemoryStream; begin    begin      str:= TMemoryStream.Create;      CurrRichRecord.richedit.Lines.SaveToStream(str);      str.Posit

模具要不要建设3D打印中心

随着3D打印技术的日益成熟与广泛应用,模具企业迎来了自建3D打印中心的热潮。这一举措不仅为企业带来了前所未有的发展机遇,同时也伴随着一系列需要克服的挑战,如何看待企业引进增材制造,小编为您全面分析。 机遇篇: 加速产品创新:3D打印技术如同一把钥匙,为模具企业解锁了快速迭代产品设计的可能。企业能够迅速将创意转化为实体模型,缩短产品从设计到市场的周期,抢占市场先机。 强化定制化服务:面

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

数据结构--二叉树(C语言实现,超详细!!!)

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具

Java项目中,配置打印 JDBC 日志的几种方法

在 IDEA 项目中,如果你想打印 JDBC 日志,可以通过配置日志框架(如 Logback 或 Log4j)来实现。Spring Boot 使用的默认日志框架是 Logback,你可以通过在 application.yml 文件中配置日志级别来打印 JDBC 日志。 方法 1: 使用 application.yml 配置 JDBC 日志 logging:level:# 显示 SQL 语句co

20190315 把整理和培养自己当作一生的事业,而不是局限在找工作拿offer。

把整理和培养自己当作一生的事业,而不是局限在找工作拿offer,做有本事的人。 来东南读研半年了,明显感觉自己掌握的不过是书本知识级别的中上水平,垃圾收集器这些的只知道背面经,靠脑子硬记,缺乏整理和系统,一头浆糊。 现在一边做实训这个烂项目,一边刷面经,一边刷剑指offer,想投些大公司的实习,又觉得还没准备好,看着各 种面经,都能说个大概,但明显感觉到自己知识的不体系和不深入,**做的项目

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ