本文共 1225 字,大约阅读时间需要 4 分钟。
题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。解题思路
设两个栈,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> Print(TreeNode pRoot) { ArrayList > res = new ArrayList >(); Stack s1 = new Stack (); Stack s2 = new Stack (); int flag = 1;//层数标签 if(pRoot == null)//为空 return res; s2.push(pRoot);//入栈,s2奇数层 ArrayList temp = new ArrayList ();//存储值得临时变量 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 (temp)); temp.clear(); flag ++; } return res; }}
转载地址:http://ltssn.baihongyu.com/