您现在的位置是:首页 > 文章详情

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

日期:2018-08-07点击:255

本文首发于我的个人博客:尾尾部落

题目描述

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

解题思路

设两个栈,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://yq.aliyun.com/articles/642743
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章