[解题思路]
二叉树的层序遍历通过使用queue来实现,
上网搜索了下,发现该题可以使用栈来解决,通过分析执行结果确实是后进先出
这里通过定义leftToRight来表示是从左到右还是从右到左
从左到右:先加left后加right
从右到左:先加right后加left
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if(root == null){ return result; } Stack<TreeNode> curLvl = new Stack<TreeNode>(); Stack<TreeNode> nextLvl = new Stack<TreeNode>(); boolean leftToRight = true; curLvl.push(root); ArrayList<Integer> output = new ArrayList<Integer>(); while(!curLvl.empty()){ TreeNode curNode = curLvl.pop(); output.add(curNode.val); if(leftToRight){ if(curNode.left != null){ nextLvl.add(curNode.left); } if(curNode.right != null){ nextLvl.add(curNode.right); } } else{ if(curNode.right != null){ nextLvl.add(curNode.right); } if(curNode.left != null){ nextLvl.add(curNode.left); } } if(curLvl.empty()){ result.add(output); output = new ArrayList<Integer>(); leftToRight = !leftToRight; curLvl.addAll(nextLvl); nextLvl.clear(); } } return result; } }