专栏首页尾尾部落[剑指offer] 按之字形顺序打印二叉树

[剑指offer] 按之字形顺序打印二叉树

题目描述

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

解题思路

设两个栈,s2存放奇数层,s1存放偶数层 遍历s2节点的同时按照左子树、右子树的顺序加入s1, 遍历s1节点的同时按照右子树、左子树的顺序加入s2

参考代码

import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        int flag = 1;
        if(pRoot == null)
            return res;
        s2.push(pRoot);
        ArrayList<Integer> temp = new ArrayList<Integer>();
        while(!s1.isEmpty() || !s2.isEmpty()){
            if(flag % 2 != 0){
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    temp.add(node.val);
                    if(node.left != null){
                        s1.push(node.left);
                    }
                    if(node.right != null){
                        s1.push(node.right);
                    }
                }
            }
            if(flag % 2 == 0){
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    temp.add(node.val);
                    if(node.right != null){
                        s2.push(node.right);
                    }
                    if(node.left != null){
                        s2.push(node.left);
                    }
                }
            }
            res.add(new ArrayList<Integer>(temp));
            temp.clear();
            flag ++;
        }
        return res;
    }

}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/printz/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [剑指offer] 把二叉树打印成多行

    就是二叉树的层序遍历,用队列来实现。我们需要两个变量,一个start记录当前层已经打印的节点个数,一个end记录前当层所有的节点个数,当 start == en...

    尾尾部落
  • [剑指offer] 二叉搜索树的第k个结点

    给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为4。

    尾尾部落
  • [剑指offer] 二叉树的深度

    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

    尾尾部落
  • 秒杀系统的设计五大原则

    1. 是指用户请求的数据能少就少,请求包括给系统发的request 及 response 。

    用户2141593
  • pandas

    pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。Pandas 纳入了大量库和一些标准的数据模型,提供了高效地操作大型数据集所需...

    润森
  • 数据结构和算法——二叉排序树

    一、二叉排序树 对于无序的序列“62,58,88,47,73,99,35,51,93,29,37,49,56,36,48,50”,是否存在一种高效的查找方案,使...

    zhaozhiyong
  • 如何降低荧光实验的自发荧光?

    现在越来越多人会在文章中加入免疫荧光图片,简化语言描述的同时也能有效提高文章档次。

    Mark Chen
  • 原 荐 Spring Boot 多库分布式事

    kinbug [进阶者]
  • Vue 中「自定义指令」的强大之处

    但是内置指令,在实际的开发过程中可能这些并不能满足所有的需求。所以 Vue 给我们提供来一个灵活的方法「自定义指令」。

    六小登登
  • json读入小结

    回家已经11点后,写一点今天工作中用到的知识,不太熟练,耽误了些时间。因为任务紧急,类似这种对某个知识点不熟练,累计叠加起来,就会导致做事变慢,最终只能靠加班。

    double

扫码关注云+社区

领取腾讯云代金券